Visible to the public Attack Graphs and Privacy, 2014

SoS Newsletter- Advanced Book Block

SoS Logo

Attack Graphs and Privacy


Security analysts use attack graphs for detection, defense, and forensics. An attack graph is defined as a representation of all paths through a system that end in a state where an intruder has successfully breached the system. Privacy needs add a complicating element to the trace. The research cited here looks at various aspects of attack graphs as they relate to privacy. All were presented in 2014.

Kiremire, A.R.; Brust, M.R.; Phoha, V.V., "Topology-Dependent Performance of Attack Graph Reconstruction in PPM-Based IP Traceback," Consumer Communications and Networking Conference (CCNC), 2014 IEEE 11th, vol., no., pp. 363, 370, 10-13 Jan. 2014. doi:10.1109/CCNC.2014.6866596
Abstract: A variety of schemes based on the technique of Probabilistic Packet Marking (PPM) have been proposed to identify Distributed Denial of Service (DDoS) attack traffic sources by IP traceback. These PPM-based schemes provide a way to reconstruct the attack graph - the network path taken by the attack traffic - hence identifying its sources. Despite the large amount of research in this area, the influence of the underlying topology on the performance of PPM-based schemes remains an open issue. In this paper, we identify three network-dependent factors that affect different PPM-based schemes uniquely giving rise to a variation in and discrepancy between scheme performance from one network to another. Using simulation, we also show the collective effect of these factors on the performance of selected schemes in an extensive set of 60 Internet-like networks. We find that scheme performance is dependent on the network on which it is implemented. We show how each of these factors contributes to a discrepancy in scheme performance in large scale networks. This discrepancy is exhibited independent of similarities or differences in the underlying models of the networks.
Keywords: computer network security; graph theory; telecommunication network routing; DDoS attack traffic sources; Internet-like networks; PPM-based IP traceback; PPM-based schemes; attack graph reconstruction; distributed denial of service attack traffic sources; large scale networks; probabilistic packet marking; topology-dependent performance; Computer crime; Convergence; IP networks; Network topology; Privacy; Topology (ID#: 15-5986)


Datta, E.; Goyal, N., "Security Attack Mitigation Framework for the Cloud," Reliability and Maintainability Symposium (RAMS), 2014 Annual, vol., no., pp. 1, 6, 27-30 Jan. 2014. doi:10.1109/RAMS.2014.6798457
Abstract: Cloud computing brings in a lot of advantages for enterprise IT infrastructure; virtualization technology, which is the backbone of cloud, provides easy consolidation of resources, reduction of cost, space and management efforts. However, security of critical and private data is a major concern which still keeps back a lot of customers from switching over from their traditional in-house IT infrastructure to a cloud service. Existence of techniques to physically locate a virtual machine in the cloud, proliferation of software vulnerability exploits and cross-channel attacks in-between virtual machines, all of these together increases the risk of business data leaks and privacy losses. This work proposes a framework to mitigate such risks and engineer customer trust towards enterprise cloud computing. Everyday new vulnerabilities are being discovered even in well-engineered software products and the hacking techniques are getting sophisticated over time. In this scenario, absolute guarantee of security in enterprise wide information processing system seems a remote possibility; software systems in the cloud are vulnerable to security attacks. Practical solution for the security problems lies in well-engineered attack mitigation plan. At the positive side, cloud computing has a collective infrastructure which can be effectively used to mitigate the attacks if an appropriate defense framework is in place. We propose such an attack mitigation framework for the cloud. Software vulnerabilities in the cloud have different severities and different impacts on the security parameters (confidentiality, integrity, and availability). By using Markov model, we continuously monitor and quantify the risk of compromise in different security parameters (e.g.: change in the potential to compromise the data confidentiality). Whenever, there is a significant change in risk, our framework would facilitate the tenants to calculate the Mean Time to Security Failure (MTTSF) cloud and allow them to adopt a dynamic mitigation plan. This framework is an add-on security layer in the cloud resource manager and it could improve the customer trust on enterprise cloud solutions.
Keywords: Markov processes; cloud computing; security of data; virtualisation; MTTSF cloud; Markov model; attack mitigation plan; availability parameter; business data leaks; cloud resource manager; cloud service; confidentiality parameter; cross-channel attacks; customer trust; enterprise IT infrastructure; enterprise cloud computing; enterprise cloud solutions; enterprise wide information processing system; hacking techniques; information technology; integrity parameter; mean time to security failure; privacy losses; private data security; resource consolidation; security attack mitigation framework; security guarantee; software products; software vulnerabilities; software vulnerability exploits; virtual machine; virtualization technology; Cloud computing; Companies; Security; Silicon; Virtual machining; Attack Graphs; Cloud computing; Markov Chain; Security; Security Administration (ID#: 15-5987)


Sarkar, A.; Kohler, S.; Riddle, S.; Ludaescher, B.; Bishop, M., "Insider Attack Identification and Prevention Using a Declarative Approach," Security and Privacy Workshops (SPW), 2014 IEEE, vol., no., pp. 265, 276, 17-18 May 2014. doi:10.1109/SPW.2014.41
Abstract: A process is a collection of steps, carried out using data, by either human or automated agents, to achieve a specific goal. The agents in our process are insiders, they have access to different data and annotations on data moving in between the process steps. At various points in a process, they can carry out attacks on privacy and security of the process through their interactions with different data and annotations, via the steps which they control. These attacks are sometimes difficult to identify as the rogue steps are hidden among the majority of the usual non-malicious steps of the process. We define process models and attack models as data flow based directed graphs. An attack A is successful on a process P if there is a mapping relation from A to P that satisfies a number of conditions. These conditions encode the idea that an attack model needs to have a corresponding similarity match in the process model to be successful. We propose a declarative approach to vulnerability analysis. We encode the match conditions using a set of logic rules that define what a valid attack is. Then we implement an approach to generate all possible ways in which agents can carry out a valid attack A on a process P, thus informing the process modeler of vulnerabilities in P. The agents, in addition to acting by themselves, can also collude to carry out an attack. Once A is found to be successful against P, we automatically identify improvement opportunities in P and exploit them, eliminating ways in which A can be carried out against it. The identification uses information about which steps in P are most heavily attacked, and try to find improvement opportunities in them first, before moving onto the lesser attacked ones. We then evaluate the improved P to check if our improvement is successful. This cycle of process improvement and evaluation iterates until A is completely thwarted in all possible ways.
Keywords: computer crime; cryptography; data flow graphs; data privacy; directed graphs; logic programming; attack model; data flow based directed graphs; declarative approach; improvement opportunities; insider attack identification; insider attack prevention; logic rules; mapping relation; nonmalicious steps; privacy; process models; security; similarity match; vulnerability analysis; Data models; Diamonds; Impedance matching; Nominations and elections; Process control; Robustness; Security; Declarative Programming; Process Modeling; Vulnerability Analysis (ID#: 15-5988)


Peipei Yi; Zhe Fan; Shuxiang Yin, "Privacy-Preserving Reachability Query Services for Sparse Graphs," Data Engineering Workshops (ICDEW), 2014 IEEE 30th International Conference on, vol., no., pp. 32, 35, March 31 2014-April 4 2014. doi:10.1109/ICDEW.2014.6818298
Abstract: This paper studies privacy-preserving query services for reachability queries under the paradigm of data outsourcing. Specifically, graph data have been outsourced to a third-party service provider (SP), query clients submit their queries to the SP, and the SP returns the query answers. However, SP may not always be trustworthy. Therefore, this paper considers protecting the structural information of the graph data and the query answers from the SP. This paper proposes simple yet optimized privacy-preserving 2-hop labeling. In particular, this paper proposes that the encrypted intermediate results of encrypted query evaluation are indistinguishable. The proposed technique is secure under chosen plaintext attack. We perform an experimental study on the effectiveness of the proposed techniques on both real-world and synthetic datasets.
Keywords: cryptography; data privacy; graph theory; query processing; data outsourcing; optimized privacy-preserving 2-hop labeling; plaintext attack; privacy-preserving reachability query services; query clients; sparse graphs; structural information; third-party service provider; Bipartite graph; Communication networks; Cryptography; Educational institutions; Labeling; Privacy; Query processing (ID#: 15-5989)


Young, A.L.; Yung, M., "The Drunk Motorcyclist Protocol for Anonymous Communication," Communications and Network Security (CNS), 2014 IEEE Conference on, vol., no., pp. 157, 165, 29-31 Oct. 2014. doi:10.1109/CNS.2014.6997482
Abstract: The buses protocol is designed to provide provably anonymous communication on a connected graph. Figuratively speaking, a bus is a single unit of transport containing multiple seats. Each seat carries a ciphertext from a sender to a receiver. The buses approach aims to conceal traffic patterns by having buses constantly travel along fixed routes and is a step forward in concealing traffic compared to other anonymous communication protocols. Therefore, in this day in which Internet privacy is crucial it deserves further investigation. Here, we cryptanalyze the reduced-seat Buses protocol and we also present distinguishing attacks against the related Taxis protocol as well as P5. These attacks highlight the need to employ cryptosystems with key-privacy in such protocols. We then show that anonymity is not formally proven in the buses protocols. These findings motivate the need for a new provably secure connectionless anonymous messaging protocol. We present what we call the drunk motorcyclist (DM) protocol for anonymous messaging that overcomes these issues. We define the DM protocol, show a construction for it, and then prove that anonymity and confidentiality hold under Decision Diffie-Hellman (DDH) against global active adversaries. Our protocol demonstrates the new principle of flooding a complete graph or an expander graph with randomly walking ciphertexts that travel until their time-to-live values expire. This principle also exhibits fault-tolerance properties.
Keywords: Internet; computer network security; cryptographic protocols; electronic messaging; motorcycles; telecommunication traffic; DDH; DM protocol; Decision Diffie-Hellman; Internet privacy; Taxis protocol; anonymous communication protocol; ciphertext; complete graph; cryptosystem; drunk motorcyclist protocol; expander graph; fault tolerance properties; key privacy; provably secure connectionless anonymous messaging protocol; reduced-seat bus protocol cryptanalyzation; time-to-live values; traffic concealment pattern; Encryption; Generators; Protocols; Public key; Receivers (ID#:15-5990)


Xin Hu; Ting Wang; Stoecklin, M.P.; Schales, D.L.; Jiyong Jang; Sailer, R., "Asset Risk Scoring in Enterprise Network with Mutually Reinforced Reputation Propagation," Security and Privacy Workshops (SPW), 2014 IEEE, vol., no., pp. 61, 64, 17-18 May 2014. doi:10.1109/SPW.2014.18
Abstract: Cyber security attacks are becoming ever more frequent and sophisticated. Enterprises often deploy several security protection mechanisms, such as anti-virus software, intrusion detection prevention systems, and firewalls, to protect their critical assets against emerging threats. Unfortunately, these protection systems are typically "noisy", e.g., regularly generating thousands of alerts every day. Plagued by false positives and irrelevant events, it is often neither practical nor cost-effective to analyze and respond to every single alert. The main challenge faced by enterprises is to extract important information from the plethora of alerts and to infer potential risks to their critical assets. A better understanding of risks will facilitate effective resource allocation and prioritization of further investigation. In this paper, we present MUSE, a system that analyzes a large number of alerts and derives risk scores by correlating diverse entities in an enterprise network. Instead of considering a risk as an isolated and static property, MUSE models the dynamics of a risk based on the mutual reinforcement principle. We evaluate MUSE with real-world network traces and alerts from a large enterprise network, and demonstrate its efficacy in risk assessment and flexibility in incorporating a wide variety of data sets.
Keywords: business data processing; firewalls; invasive software; risk analysis; MUSE; antivirus software; asset risk scoring; cyber security attacks; enterprise network; firewalls; intrusion detection-prevention systems; mutually reinforced reputation propagation; risk assessment; security protection mechanisms; Belief propagation; Bipartite graph; Data mining; Intrusion detection; Malware; Servers; Risk Scoring; mutually reinforced principles; reputation propagation (ID#: 15-5991)


Shan Chang; Hongzi Zhu; Mianxiong Dong; Ota, K.; Xiaoqiang Liu; Guangtao Xue; Xuemin Shen, "BusCast: Flexible and Privacy Preserving Message Delivery Using Urban Buses," Parallel and Distributed Systems (ICPADS), 2014 20th IEEE International Conference on, vol., no., pp. 502, 509, 16-19 Dec. 2014. doi:10.1109/PADSW.2014.7097847
Abstract: With the popularity of intelligent mobile devices, enormous urban information has been generated and required by the public. In response, ShanghaiGrid (SG) aims to providing abundant information services to the public. With fixed schedule and urban-wide coverage, an appealing service in SG is to provide free message delivery service to the public using buses, which allows mobile device users to send messages to locations of interest via buses. The main challenge in realizing this service is to provide efficient routing scheme with privacy preservation under highly dynamic urban traffic condition. In this paper, we present an innovative scheme BusCast to tackle this problem. In BusCast, buses can pick up and forward personal messages to their destination locations in a store-carry-forward fashion. For each message, BusCast conservatively associates a routing graph rather than a fixed routing path with the message in order to adapt the dynamic of urban traffic. Meanwhile, the privacy information about the user and the message destination is concealed from both intermediate relay buses and outside adversaries. Both rigorous privacy analysis and extensive trace-driven simulations demonstrate the efficacy of BusCast scheme.
Keywords: data privacy; traffic engineering computing; transportation; BusCast scheme; ShanghaiGrid; information service; intelligent mobile device; message destination; privacy analysis; privacy information; privacy preserving message delivery; routing graph; routing scheme; trace-driven simulation; urban bus; urban traffic condition; Bismuth; Delays; Relays; Routing; anonymous communication; backward unlinkability; message delivery; traffic analysis attacks; vehicular networks (ID#: 15-5992)


Maag, M.L.; Denoyer, L.; Gallinari, P., "Graph Anonymization Using Machine Learning," Advanced Information Networking and Applications (AINA), 2014 IEEE 28th International Conference on, vol., no., pp. 1111, 1118, 13-16 May 2014. doi:10.1109/AINA.2014.20
Abstract: Data privacy is a major problem that has to be considered before releasing datasets to the public or even to a partner company that would compute statistics or make a deep analysis of these data. This is insured by performing data anonymization as required by legislation. In this context, many different anonymization techniques have been proposed in the literature. These methods are usually specific to a particular de-anonymization procedure--or attack--one wants to avoid, and to a particular known set of characteristics that have to be preserved after the anonymization. They are difficult to use in a general context where attacks can be of different types, and where measures are not known to the anonymizer. The paper proposes a novel approach for automatically finding an anonymization procedure given a set of possible attacks and a set of measures to preserve. The approach is generic and based on machine learning techniques. It allows us to learn directly an anonymization function from a set of training data so as to optimize a trade off between privacy risk and utility loss. The algorithm thus allows one to get a good anonymization procedure for any kind of attacks, and any characteristic in a given set. Experiments made on two datasets show the effectiveness and the genericity of the approach.
Keywords: data privacy; graph theory; learning (artificial intelligence); risk management; data anonymization; de-anonymization procedure; graph anonymization; machine learning; privacy risk; training data; utility loss; Context; Data privacy; Loss measurement; Machine learning algorithms; Noise; Privacy; Social network services; Graph Anonymization; Machine Learning; Privacy (ID#:15-5993)


Articles listed on these pages have been found on publicly available internet pages and are cited with links to those pages. Some of the information included herein has been reprinted with permission from the authors or data repositories. Direct any requests via Email to for removal of the links or modifications to specific citations. Please include the ID# of the specific citation in your correspondence.