Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

Competition Numbers, Quasi-Line Graphs and Holes ; ; Schweitzer, Patrick in SIAM Journal on Discrete Mathematics (in press) The competition graph of an acyclic directed graph D is the undirected graph on the same vertex set as D in which two distinct vertices are adjacent if they have a common out-neighbor in D. The ... [more ▼] The competition graph of an acyclic directed graph D is the undirected graph on the same vertex set as D in which two distinct vertices are adjacent if they have a common out-neighbor in D. The competition number of an undirected graph G is the least number of isolated vertices that have to be added to G to make it the competition graph of an acyclic directed graph. We resolve two conjectures concerning competition graphs. First we prove a conjecture of Opsut by showing that the competition number of every quasi-line graph is at most 2. Recall that a quasi-line graph, also called a locally co-bipartite graph, is a graph for which the neighborhood of every vertex can be partitioned into at most two cliques. To prove this conjecture we devise an alternative characterization of quasi-line graphs to the one by Chudnovsky and Seymour. Second, we prove a conjecture of Kim by showing that the competition number of any graph is at most one greater than the number of holes in the graph. Our methods also allow us to prove a strengthened form of this conjecture recently proposed by Kim, Lee, Park and Sano, showing that the competition number of any graph is at most one greater than the dimension of the subspace of the cycle space spanned by the holes. [less ▲] Detailed reference viewed: 145 (7 UL)A Probabilistic Framework for Security Scenarios with Dependent Actions Kordy, Barbara ; Schweitzer, Patrick ; Pouly, Marc in The 11th International Conference on Integrated Formal Methods (iFM'14), Bertinoro, Italy (2014) Detailed reference viewed: 64 (1 UL)ADTool: Security Analysis with Attack-Defense Trees (Tool Demonstration Paper) Kordy, Barbara ; Kordy, Piotr ; Mauw, Sjouke et al in 10th International Conference on Quantitative Evaluation of SysTems (2013) The ADTool is free, open source software assisting graphical modeling and quantitative analysis of security, using attack-defense trees. The main features of the ADTool are easy creation, efficient ... [more ▼] The ADTool is free, open source software assisting graphical modeling and quantitative analysis of security, using attack-defense trees. The main features of the ADTool are easy creation, efficient editing, and automated bottom-up evaluation of security-relevant measures. The tool also supports the usage of attack trees, protection trees and defense trees, which are all particular instances of attack-defense trees. [less ▲] Detailed reference viewed: 73 (7 UL)On Beta Models with Trust Chains Muller, Tim ; Schweitzer, Patrick in Proceedings of the 7th IFIP WG 11.11 International Conference on Trust Management (2013) In a type of interactions over the Internet, a user (the subject) is dependent on another user (the target), but not vice versa. The subject should therefore form an opinion about the target, before ... [more ▼] In a type of interactions over the Internet, a user (the subject) is dependent on another user (the target), but not vice versa. The subject should therefore form an opinion about the target, before possibly initiating an interaction. The scenario wherein a subject only relies on information obtained from past interactions with the target, is well-studied and understood. In this paper, we formally analyze the implication of allowing recommendations (statements of a third party) as source of information. We identify the family of valid models that admit recommendations. This allows us to verify particular existing models that admit recommendations. [less ▲] Detailed reference viewed: 21 (2 UL)Attack-Defense Trees Kordy, Barbara ; Mauw, Sjouke ; Radomirovic, Sasa et al in Journal of Logic & Computation (2012) Attack-defense trees are a novel methodology for graphical security modeling and assessment. They extend the well known formalism of attack trees by allowing nodes that represent defensive measures to ... [more ▼] Attack-defense trees are a novel methodology for graphical security modeling and assessment. They extend the well known formalism of attack trees by allowing nodes that represent defensive measures to appear at any level of the tree. This enlarges the modeling capabilities of attack trees and makes the new formalism suitable for representing interactions between an attacker and a defender. Our formalization supports different semantical approaches for which we provide usage scenarios. We also formalize how to quantitatively analyze attack and defense scenarios using attributes. [less ▲] Detailed reference viewed: 168 (14 UL)A Formal Derivation of Composite Trust Muller, Tim ; Schweitzer, Patrick in Foundations and Practice of Security - 5th International Symposium, FPS 2012, Montreal, QC, Canada, October 25-26, 2012, Revised Selected Papers (2012) Trust appears in asymmetric interactions, where one party (the active party) can easily betray a stakeholder (the passive party). Over the Internet, the amount of information that a passive party can use ... [more ▼] Trust appears in asymmetric interactions, where one party (the active party) can easily betray a stakeholder (the passive party). Over the Internet, the amount of information that a passive party can use to determine the integrity of an active party, is often limited. The scenario where there is only one passive party and one active party is well studied, and has been solved under some assumptions. We generalize the setting to allow for more parties. In particular, the paper contains a formal derivation of conjunction and disjunction of trust opinions. [less ▲] Detailed reference viewed: 49 (2 UL)Quantitative Questions on Attack-Defense Trees Kordy, Barbara ; Mauw, Sjouke ; Schweitzer, Patrick Report (2012) Detailed reference viewed: 59 (1 UL)Quantitative Questions on Attack-Defense Trees Kordy, Barbara ; Mauw, Sjouke ; Schweitzer, Patrick in Information Security and Cryptology - ICISC 2012 - 15th International Conference, Seoul, Korea, November 28-30, 2012, Revised Selected Papers (2012) Attack-defense trees are a novel methodology for graphical security modeling and assessment. The methodology includes intuitive and formal components that can be used for quantitative analysis of attack ... [more ▼] Attack-defense trees are a novel methodology for graphical security modeling and assessment. The methodology includes intuitive and formal components that can be used for quantitative analysis of attack-defense scenarios. In practice, we use intuitive questions to ask about aspects of scenarios we are interested in. Formally, a computational procedure, using a bottom-up algorithm, is applied to derive the corresponding numerical values. This paper bridges the gap between the intuitive and the formal way of quantitatively assessing attack-defense scenarios. We discuss how to properly specify a question, so that it can be answered unambiguously. Given a well-specified question, we then show how to derive an appropriate attribute domain which constitutes the corresponding formal model. [less ▲] Detailed reference viewed: 76 (3 UL)Attribute Decoration of Attack-Defense Trees ; Kordy, Barbara ; et al in International Journal of Secure Software Engineering (2012), 3(2), 1-35 Attack-defense trees can be used as part of threat and risk analysis for system development and maintenance. They are an extension of attack trees with defense measures. Moreover, tree nodes can be ... [more ▼] Attack-defense trees can be used as part of threat and risk analysis for system development and maintenance. They are an extension of attack trees with defense measures. Moreover, tree nodes can be decorated with attributes, such as probability, impact and penalty, to increase the expressiveness of the model. Attribute values are typically assigned based on cognitive estimations and historically recorded events. This paper presents a practical case study with attack-defense trees. First, we create an attack-defense tree for an RFID-based goods management system for a warehouse. Then, we explore how to use a rich set of attributes for attack and defense nodes and how to assign and aggregate values to obtain condensed information, such as performance indicators or other key security figures. We discuss different modeling choices and trade-offs. The case study led us to define concrete guidelines that can be used by software developers, security analysts and system owners when performing similar assessments. [less ▲] Detailed reference viewed: 56 (2 UL)Computational Aspects of Attack-Defense Trees Kordy, Barbara ; Pouly, Marc ; Schweitzer, Patrick in Security and Intelligent Information Systems - International Joint Conferences, SIIS 2011, Warsaw, Poland, June 13-14, 2011, Revised Selected Papers (2011) Attack-defense trees extend attack trees with defense nodes. This richer formalism allows for a more precise modeling of a system’s vulnerabilities, by representing interactions between possible attacks ... [more ▼] Attack-defense trees extend attack trees with defense nodes. This richer formalism allows for a more precise modeling of a system’s vulnerabilities, by representing interactions between possible attacks and corresponding defensive measures. In this paper we compare the computational complexity of both formalisms. We identify semantics for which extending attack trees with defense nodes does not increase the computational complexity. This implies that, for these semantics, every query that can be solved efficiently on attack trees can also be solved efficiently on attack-defense trees. Furthermore, every algorithm for attack trees can directly be used to process attack-defense trees. [less ▲] Detailed reference viewed: 58 (3 UL)Foundations of Attack-Defense Trees Kordy, Barbara ; Mauw, Sjouke ; Radomirovic, Sasa et al in Proceedings of the 7th International Workshop on Formal Aspects of Security and Trust (2010) We introduce and give formal definitions of attack–defense trees. We argue that these trees are a simple, yet powerful tool to analyze complex security and privacy problems. Our formalization is generic ... [more ▼] We introduce and give formal definitions of attack–defense trees. We argue that these trees are a simple, yet powerful tool to analyze complex security and privacy problems. Our formalization is generic in the sense that it supports different semantical approaches. We present several semantics for attack–defense trees along with usage scenarios, and we show how to evaluate attributes. [less ▲] Detailed reference viewed: 75 (3 UL)Attack-Defense Trees and Two-Player Binary Zero-Sum Extensive Form Games Are Equivalent Kordy, Barbara ; Mauw, Sjouke ; Melissen, Matthijs et al in Proceedings of GameSec 2010 (2010) Attack-defense trees are used to describe security weaknesses of a system and possible countermeasures. In this paper, the connection between attack-defense trees and game theory is made explicit. We show ... [more ▼] Attack-defense trees are used to describe security weaknesses of a system and possible countermeasures. In this paper, the connection between attack-defense trees and game theory is made explicit. We show that attack-defense trees and binary zero-sum two-player extensive form game have equivalent expressive power when considering satisfiability, in the sense that they can be converted into each other while preserving their outcome and their internal structure. [less ▲] Detailed reference viewed: 99 (8 UL)Connecting face hitting sets in planar graphs ; Schweitzer, Patrick in Information Processing Letters (2010), 111(1), 11-15 We show that any face hitting set of size n of a connected planar graph with a minimum degree of at least 3 is contained in a connected subgraph of size 5n−6. Furthermore we show that this bound is tight ... [more ▼] We show that any face hitting set of size n of a connected planar graph with a minimum degree of at least 3 is contained in a connected subgraph of size 5n−6. Furthermore we show that this bound is tight by providing a lower bound in the form of a family of graphs. This improves the previously known upper and lower bound of 11n−18 and 3n respectively by Grigoriev and Sitters. Our proof is valid for simple graphs with loops and generalizes to graphs embedded in surfaces of arbitrary genus. [less ▲] Detailed reference viewed: 65 (2 UL)The optimal size of a permit market ; Schweitzer, Patrick in Journal of Environmental Economics and Management [= JEEM] (2010), 60(2), 133-143 Regulating the emissions of non-uniformly mixed pollutants with a permit market carries the risk of hot spot formation, which can be reduced by dividing the regulation area into trading zones. The trading ... [more ▼] Regulating the emissions of non-uniformly mixed pollutants with a permit market carries the risk of hot spot formation, which can be reduced by dividing the regulation area into trading zones. The trading zone approach has been extensively discussed for the full-information case. We consider incomplete information concerning the emitters’ abatement costs, their locations, and pollution dispersion. We derive the optimal number of trading zones and the optimal number of permits per zone and analyze under which conditions a system of independent trading zones is superior to other policy measures. Our results show that appropriately sized permit markets are well-suited to regulating non-uniformly mixed pollutants under informational constraints if firms are not too heterogeneous. Only for substantial heterogeneity and a highly non-linear damage function can it be optimal to use command-and-control strategies. [less ▲] Detailed reference viewed: 77 (3 UL) |
||