Graphs

Investigating the prior research that has been conducted with graphs and security policy modeling, or more generally, graphs and security research, even further abstracted graph-based languages.

Keywords/ main reseach areas:

• Vulnerabilty/violation
• Attack graph
• Transformation, morphism
• State-based approach
• Policy anaylsis
• Code analysis
• modeling interconnection networks
  

Darmaillacq, "Security policy testing using vulnerability exploit chaining", ICSTW'08.

• Short paper (2 pages)
• Looks like they just made up their security requirements (policy statements), and encoded them arbitrarily, but I don't know, perhaps this is standardized.
• "test purpose" - "a sequence of events, of which occurrence during a test execution guarantees deliverance of a verdict (pass or fail)." -- doesn't handle NFRs, but enables their policy statements to be encoded in a graph that can be traversed. If you get to a specific sink node then you know that a violation has occurred.
• Combines this research with an attack graph

Bahati, Bauer, "Adapting to Run-time changes in policies driving autonomic management", ICAS 2008

• Has a strange reinforcement learning approach
• I really only pulled this paper as an example for the use of state transition diagrams as graphs in security research.
  
• They express the policy, then generate states that would satisfy the policy, then have violation states, then generate the graph, and see if the states are reachable. Its from an execution standpoint though, I think, not a design/architecture view.
  

Ahn, Xu, Zhang, "Systematic Policy Analysis for High-assurance Services in SELinux", 2008 IEEE Workshop on Policies for Distributed Systems and Networks

• Probably the most relevant paper to what we're doing although its targeted to SELinux/OS specific work.
• Interesting because they have XML policy representation and an architecture that automatically translates it into graph language
• They have a visual representation for violations too, this paper needs a more thurough read-through

Zhao, Ma, Liu, Hi, Huang, "A Graph Transformation based Approach for Runtime Constrained Evoluation of Service-Oritend Architectures", 2009 Parallel, Distributed and Networked-based Processing

• "Dynamic software architectures [4] are those architectures that modify their architecture and enact the modifcations during the system's execution. This behavior is most commonly know as run-time evoluation or dynamism. Graph-based dyamical reconfguration of architectures [12, 17, 20] provides both a formal basis and a graphical representation that is the usualy way architecture are represented."
• Their graph as a service with different ports and a "channel" that connects the ports. It's pretty easy to visualize the system. The whole system has a formal backing.
• SOA Evoluation gets pretty messy though, There are productions and morphisms that make the graph (even a simple example) ... well, complicated. It almost doesn't seem as if their graph is even showing the entire architecure, just a subset. The whole transformation based approach doesn't seem the exact right fit for what we are attempting to do.

Duan, Feng, Wang, Zhang, Yew, "Detecting and eliminating potential violation of sequential consistency for concurrent C/C++ programs" 2009 international symp. on code generation and optimization

• This is the paper that led me down the path of looking for graphs and violation analysis, although the paper itself didn't really give me much to go on itself.
• They have graphs that model executable code and some examples that detect race conditions

Shih, Tan, "Fault-tolerant maximal local-connectivity on the bubble sort graphs", 2009 sixth international conference on information technolgy: new generations

• Similar to the last paper this one didn't really specifically apply to our work but I'm including it for an idea
• "Interconnection network is usually modeled as a graph, in which vertices and edges correspond to processor and communication links, respectively."

Najumudheen, Mall, Samanta, "A Dependence Graph-based Test coverage analysis technique for Object-oritented programs", 2009 Sixth International Conference on Information Technology: New Generations"

• Call Based Object Oritented System Dependence Graph (COSDG)
• "COSDG is a directed, connected multigraph G = (V,E), consisting of a set of V of vertices and set E of edges. A vertex represents one of three categories: statement, entry, and parameter vertices. An edge represents control, data dependency, parameter dependency, method call dependency, summary, class, and inheritance." - We wouldn't need all of that but I like that they can isolate their descriptions of a system down to these fine-grained details.
• Of course their reseach is more based on code coverage for testing but it could easily be adapted to explain the architecture of a system.
  

Wermelinger, Lopes, Fiadeiro, "A graph based architectural (re)configuration language", ESEC/FSE 2001.

• I only pulled this paper because it had reconfiguration and graph in it, I'm not sure if it has anything to do with security or policy modeling.
• This paper is about CommUnity but after just glancing through it I can't exactly figure out what the paper is adding. It seems to be an update of an earlier publication they had on reconfiguration and how existing approaches didn't correclty model reconfiguraiton. It doesn't exactly look like they're extending unity but instead just trying to use it in a new novel way perhaps.
  
• "algebraic graph rewriting" -- similar to a calculus graph rewriting approach?