2009 Technical Reports

Department of Computing and Information Sciences
Kansas State University

Report 2009-1 Abstract Interpretation from a Topological Perspective by David A. Schmidt
Abstract: Topology is the study of property sets (open sets) and continuous functions on them. Despite its applicability to abstract interpretation, topology is little used, and this paper tries to rectify the situation: We develop abstract interpretation from topological principles by relaxing the definitions of open set and continuity; key results still hold. We study families of closed and open sets and show they generate post- and pre-condition analyses, respectively. Giacobazzi's forwards- and backwards-complete functions are characterized by the topologically closed and continuous maps. Finally, we show that Smyth's upper and lower topologies for powersets induce the overapproximating and underapproximating transition functions used for abstract-model checking.

Report 2009-2 Report 2009-2. Abstract parsing: static analysis of dynamically generated string output using LR-parsing technology by Kyung-Goo Doh, Hyunha Kim, and David A. Schmidt
Abstract: We combine LR(k)-parsing technology and data-flow analysis to analyze, in advance of execution, the documents generated dynamically by a program. Based on the document language's context-free reference grammar and the program's control structure, the analysis predicts how the documents will be generated and parses the predicted documents. This simultaneous analyze-and-parse strategy gives better precision than an analyze-then-parse strategy because it computes {\em abstract parse stacks}, which encode a generated document's context-free structure. The technique is implemented in Objective Caml and has been tested to statically validate the syntax of HTML documents dynamically generated by PHP programs.

Report 2009-3 A Sound and Practical Approach to Quantifying Security Risk in Enterprise Networks by John Homer, Xinming Ou, and David Schmidt
Abstract: Mitigation of security risk is an important task in enterprise network security management. However it is presently a skill acquired by individual experience, more an art than a science. The biggest challenge in the problem is a quantitative model that objectively measures the likelihood a breach can be accomplished. This paper presents a sound and practical approach to such a quantitativemodel. We utilize existing work in attack graphs and individual vulnerability metrics, such as CVSS, and apply probabilistic reasoning to produce a sound risk measurement. The problem requires a careful coordination of attack graph data to account for cyclic and shared dependencies. We recognize that networks commonly have many host interconnections and network privileges could be gained in many ways. This factor leads to cycles in an attack graph, which must be identified and properly treated when measuring risk to prevent distortion of the results. We also recognize that multiple attack paths leading to the same network privilege will often share some dependencies and so a valid assessment cannot simply treat these paths as independent. Our approach is provably sound and ensures that shared dependencies have a proportional effect on the final calculation, and that cycles are handled correctly so that privileges are evaluated without any self-referencing effect. We also present preliminary experimental results on our algorithm and identify directions for future improvement.