This proposal is concerned with formal modeling of risk analysis as it relates to the security of systems. Risk analysis in the literature has focused on offline computations in conjunction with a manual response. We propose a real-time approach to risk management by dynamically trading utility for security. A consequence of our approach is that it provides users with the maximum possible functionality for any predefined level of risk tolerance. We model risk management through flow adjustment in a tripartite graphs, with the partitions corresponding to threats, permissions and assets in the system. The focus is on establishing the complexities for the various flow queries in this setting. We have already established that some of the problems in this setting are weakly NP-complete and this raises the possibility of designing polynomial approximation schemes for them.
In this proposal, we formally studied the problem of managing the risk of information systems. Our risk management model uses computation of risk to drive changes in the security posture of a system and therefore, allows risk management to occur in real time in order to reduce the window of exposure. Our model minimizes the tension between security and usability by trading them dynamically. We model the performance-sensitive runtime risk management of information systems as a generalization of the classical Vertex Cover Problem (VC), which is referred as the extit{Partial Vertex Cover Problem} (PVC). In the PVC problem, we are given an undirected graph G and an integer t, and the goal is to select a minimum subset of vertices that covers all but t edges. We study the computational complexity and approximability of the PVC problem and generalizations of the PVC problem, where either the vertices, the edges, or both are weighted.We have shown that the PVC problem on bipartite graphs is NP-hard, even if the graph is unweighted. This should be contrasted to the VC problem onbipartite graphs, which is known to be solvable in polynomial time, on account of the total unimodularity of the constraint matrix. We have also designed an LP-rounding based 1.71-approximation algorithms for the variants of the PVC problem considered. As part of the project, we also studied a problem closely related to system security, which we refer to as the Weighted Optimal Length Resolution Refutation Problem (WOLRR). The optimization version of the WOLRR problem is to find the weighted optimal length resolution refutation of a system of difference constraints over an integral domain using the Fourier-Motzkin (FM) elimination procedure. Although the FM elimination procedure cannot be applied to integer programs in general, FM is a sound and complete procedure for difference constraint systems (DCS), since the constraint matrix of a DCS is totally unimodular. The literature has already established that every DCS has a short refutation. However, computing the weighted optimal length resolution refutation (WOLRR) is {f NP-hard}. As part of this project, we designed both a fully polynomial-time approximation scheme (FPTAS) for computing the WOLRR of a given weighted difference constraint system (WDCS). The intellectual merit of this proposal is as follows: egin{enumerate}[(i)]item A new, rigorous model for the risk management problem has been proposed.item A large number of combinatorial optimization problems that have arisen in this model have beenproperly characterized.item Simulations of our approaches for the partial vertex cover problem have been built and tested.item Our work serves to bridge the gap between the theoretical field of combinatorial optimization andthe applied field of computer security.end{enumerate} The broader impact of this project is multidimensional.It served to significantly advance learning and discovery in analysis, algorithms, and implementations,which also resulted in writingand publishing high quality papers. The PI, his postdoctoral associate, and the collaborators who worked for this projecthave a paper published in {em Computer Networks} and are currently preparing another manuscript onWeighted Optimal Length Resolution Refutation. Moreover, this project effectively integrated education and research to train undergraduate and graduate students and to promote a thriving and active computer science program at West Virginia University. The PI will be teachinga course on ``Approximation Algorithms'' in Spring 2014.The courses taught by the PI have improved students' abilities to conduct research and communicatethe results to their peers. Furthermore, the project facilitated the development of collaborative relationships with research laboratories and other academic institutions,thereby enhancing the local research infrastructure. The PI collaborated with severalresearchers from other universities and laboratories including Sandia National Laboratories and U. California, Berkeley. Thus, this project impacted research activities not only in West Virginia, but alsonationally and internationally.
