Search

We consider the minimum spanning tree problem in a setting where the edge weights are stochastic from unknown distributions, and the only available information is a single sample of each edge's weight distribution. In this setting, we analyze the expected performance of the algorithm that outputs a minimum spanning tree for the sampled weights. We compare to the optimal solution when the distributions are known. For every graph with weights that are exponentially distributed, we show that the sampling based algorithm has a performance guarantee that is equal to the size of the largest bond in the graph. Furthermore, we show that for every graph this performance guarantee is tight. The proof is based on two separate inductive arguments via edge contractions, which can be interpreted as reducing the spanning tree problem to a stochastic item selection problem. We also generalize these results to arbitrary matroids, where the performance guarantee is equal to the size of the largest co-circuit of the matroid.

Researchers in the highly active field of intrusion detection largely rely on public datasets for their experimental evaluations. However, the large number of existing datasets, the discovery of previously unknown flaws therein, and the frequent publication of new datasets make it hard to select suitable options and sufficiently understand their respective limitations. Hence, there is a great risk of drawing invalid conclusions from experimental results with respect to detection performance of novel methods in the real world. While there exist various surveys on intrusion detection datasets, they have deficiencies in providing researchers with a profound decision basis since they lack comprehensiveness, actionable details, and up-to-dateness. In this paper, we present COMIDDS, an ongoing effort to comprehensively survey intrusion detection datasets with an unprecedented level of detail, implemented as a website backed by a public GitHub repository. COMIDDS allows researchers to quickly identify suitable datasets depending on their requirements and provides structured and critical information on each dataset, including actual data samples and links to relevant publications. COMIDDS is freely accessible, regularly updated, and open to contributions., Comment: To be published in Proceedings of the 17th Cyber Security Experimentation and Test Workshop (CSET 2024)

We consider competitive facility location as a two-stage multi-agent system with two types of clients. For a given host graph with weighted clients on the vertices, first facility agents strategically select vertices for opening their facilities. Then, the clients strategically select which of the opened facilities in their neighborhood to patronize. Facilities want to attract as much client weight as possible, clients want to minimize congestion on the chosen facility. All recently studied versions of this model assume that clients can split their weight strategically. We consider clients with unsplittable weights but allow mixed strategies. So clients may randomize over which facility to patronize. Besides modeling a natural client behavior, this subtle change yields drastic changes, e.g., for a given facility placement, qualitatively different client equilibria are possible. As our main result, we show that pure subgame perfect equilibria always exist if all client weights are identical. For this, we use a novel potential function argument, employing a hierarchical classification of the clients and sophisticated rounding in each step. In contrast, for non-identical clients, we show that deciding the existence of even approximately stable states is computationally intractable. On the positive side, we give a tight bound of $2$ on the price of anarchy which implies high social welfare of equilibria, if they exist., Comment: full version of the article at the 33rd International Joint Conference on Artificial Intelligence (IJCAI-2024)

Cyberattacks have grown into a major risk for organizations, with common consequences being data theft, sabotage, and extortion. Since preventive measures do not suffice to repel attacks, timely detection of successful intruders is crucial to stop them from reaching their final goals. For this purpose, many organizations utilize Security Information and Event Management (SIEM) systems to centrally collect security-related events and scan them for attack indicators using expert-written detection rules. However, as we show by analyzing a set of widespread SIEM detection rules, adversaries can evade almost half of them easily, allowing them to perform common malicious actions within an enterprise network without being detected. To remedy these critical detection blind spots, we propose the idea of adaptive misuse detection, which utilizes machine learning to compare incoming events to SIEM rules on the one hand and known-benign events on the other hand to discover successful evasions. Based on this idea, we present AMIDES, an open-source proof-of-concept adaptive misuse detection system. Using four weeks of SIEM events from a large enterprise network and more than 500 hand-crafted evasions, we show that AMIDES successfully detects a majority of these evasions without any false alerts. In addition, AMIDES eases alert analysis by assessing which rules were evaded. Its computational efficiency qualifies AMIDES for real-world operation and hence enables organizations to significantly reduce detection blind spots with moderate effort., Comment: To be published in Proceedings of the 33rd USENIX Security Symposium (USENIX Security 2024)

This paper revisits the well known single machine scheduling problem to minimize total weighted completion times. The twist is that job sizes are stochastic from unknown distributions, and the scheduler has access to only a single sample from each of the distributions. For this restricted information regime, we analyze the simplest and probably only reasonable scheduling algorithm, namely to schedule by ordering the jobs by weight over sampled processing times. In general, this algorithm can be tricked by adversarial input distributions, performing in expectation arbitrarily worse even in comparison to choosing a random schedule. The paper suggests notions to capture the idea that this algorithm, on reasonable inputs, should exhibit a provably good expected performance. Specifically, we identify three natural classes of input distributions, such that for these classes, the algorithm performs better than random on any input., Comment: 12 pages, 1 figure

This paper addresses the optimization problem to maximize the total costs that can be shared among a group of agents, while maintaining stability in the sense of the core constraints of a cooperative transferable utility game, or TU game. When maximizing total shareable costs, the cost shares must satisfy all constraints that define the core of a TU game, except for being budget balanced. The paper first gives a fairly complete picture of the computational complexity of this optimization problem, its relation to optimiztion over the core itself, and its equivalence to other, minimal core relaxations that have been proposed earlier. We then address minimum cost spanning tree (MST) games as an example for a class of cost sharing games with non-empty core. While submodular cost functions yield efficient algorithms to maximize shareable costs, MST games have cost functions that are subadditive, but generally not submodular. Nevertheless, it is well known that cost shares in the core of MST games can be found efficiently. In contrast, we show that the maximization of shareable costs is NP-hard for MST games and derive a 2-approximation algorithm. Our work opens several directions for future research., Comment: 15 pages, 2 figures

This paper gives a complete analysis of worst-case equilibria for various versions of weighted congestion games with two players and affine cost functions. The results are exact price of anarchy bounds which are parametric in the weights of the two players, and establish exactly how the primitives of the game enter into the quality of equilibria. Interestingly, some of the worst-cases are attained when the players' weights only differ slightly. Our findings also show that sequential play improves the price of anarchy in all cases, however, this effect vanishes with an increasing difference in the players' weights. Methodologically, we obtain exact price of anarchy bounds by a duality based proof mechanism, based on a compact linear programming formulation that computes worst-case instances. This mechanism yields duality-based optimality certificates which can eventually be turned into purely algebraic proofs., Comment: 17 pages, 9 figures, 4 tables

Artifacts such as log data and network traffic are fundamental for cybersecurity research, e.g., in the area of intrusion detection. Yet, most research is based on artifacts that are not available to others or cannot be adapted to own purposes, thus making it difficult to reproduce and build on existing work. In this paper, we identify the challenges of artifact generation with the goal of conducting sound experiments that are valid, controlled, and reproducible. We argue that testbeds for artifact generation have to be designed specifically with reproducibility and adaptability in mind. To achieve this goal, we present SOCBED, our proof-of-concept implementation and the first testbed with a focus on generating realistic log data for cybersecurity experiments in a reproducible and adaptable manner. SOCBED enables researchers to reproduce testbed instances on commodity computers, adapt them according to own requirements, and verify their correct functionality. We evaluate SOCBED with an exemplary, practical experiment on detecting a multi-step intrusion of an enterprise network and show that the resulting experiment is indeed valid, controlled, and reproducible. Both SOCBED and the log dataset underlying our evaluation are freely available., Comment: To be published in Proceedings of the 2021 Annual Computer Security Applications Conference (ACSAC '21)

We introduce set packing games as an abstraction of situations in which $n$ selfish players select subsets of a finite set of indivisible items, and analyze the quality of several equilibria for this class of games. Assuming that players are able to approximately play equilibrium strategies, we show that the total quality of the resulting equilibrium solutions is only moderately suboptimal. Our results are tight bounds on the price of anarchy for three equilibrium concepts, namely Nash equilibria, subgame perfect equilibria, and an equilibrium concept that we refer to as $k$-collusion Nash equilibrium.

In this paper, we analyze the Common Platform Enumeration (CPE) dictionary and the Common Vulnerabilities and Exposures (CVE) feeds. These repositories are widely used in Vulnerability Management Systems (VMSs) to check for known vulnerabilities in software products. The analysis shows, among other issues, a lack of synchronization between both datasets that can lead to incorrect results output by VMSs relying on those datasets. To deal with these problems, we developed a method that recommends to a user a prioritized list of CPE identifiers for a given software product. The user can then assign (and, if necessary, adapt) the most suitable CPE identifier to the software so that regular (e.g., daily) checks can find known vulnerabilities for this software in the CVE feeds. Our evaluation of this method shows that this interaction is indeed necessary because a fully automated CPE assignment is prone to errors due to the CPE and CVE shortcomings. We implemented an open-source VMS that employs the proposed method and published it on GitHub.

This paper establishes performance guarantees for online algorithms that schedule stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required linear or convex programming relaxations for the assignment of jobs to machines. The algorithms introduced in this paper are purely combinatorial. The performance bounds are of the same order of magnitude as those of earlier work, and depend linearly on an upper bound on the squared coefficient of variation of the jobs' processing times. Specifically for deterministic processing times, without and with release times, the competitive ratios are 4 and 7.216, respectively. As to the technical contribution, the paper shows how dual fitting techniques can be used for stochastic and nonpreemptive scheduling problems., Comment: Preliminary version appeared in IPCO 2017

In \cite{EK10} the use of VCG in matching markets is motivated by saying that in order to compute market clearing prices in a matching market, the auctioneer needs to know the true valuations of the bidders. Hence VCG and corresponding personalized prices are proposed as an incentive compatible mechanism. The same line of argument pops up in several lecture sheets and other documents related to courses based on Easley and Kleinberg's book, seeming to suggest that computing market clearing prices and corresponding assignments were \emph{not} incentive compatible. Main purpose of our note is to observe that, in contrast, assignments based on buyer optimal market clearing prices are indeed incentive compatible.