PAGE: A Partition Aware Engine for Parallel Graph Computation

Abstract

Graph partition quality affects the overall performance of parallel graph computation systems. The quality of a graph partition is measured by the balance factor and edge cut ratio. A balanced graph partition with small edge cut ratio is generally preferred since it reduces the expensive network communication cost. However, according to an empirical study on Giraph, the performance over well partitioned graph might be even two times worse than simple random partitions. This is because these systems only optimize for the simple partition strategies and cannot efficiently handle the increasing workload of local message processing when a high quality graph partition is used. In this paper, we propose a novel partition aware graph computation engine named PAGE, which equips a new message processor and a dynamic concurrency control model. The new message processor concurrently processes local and remote messages in a unified way. The dynamic model adaptively adjusts the concurrency of the processor based on the online statistics. The experimental evaluation demonstrates the superiority of PAGE over the graph partitions with various qualities.

Aim

The main aim is to generate PAGE for an efficient and general parallel graph computation engine.

Scope

A partition aware graph computation engine named PAGE that monitors three high-level key running metrics and dynamically adjusts the system configurations.

Existing System

Graph computation systems. Parallel graph computation is a popular technique to process and analyze large scale graphs. Different from traditional big data analysis frameworks (e.g., Map Reduce), most of graph computation systems store graph data in memory and cooperate with other computing nodes via message passing interface. Besides, these systems adopt the vertex-centric programming model and release users from the tedious communication protocol. Such systems can also provide fault-tolerant and high scalability compared to the traditional graph processing libraries, such as Parallel BGL and CGMgraph. There exist several excellent systems, like Pregel, Giraph, GPS, Trinity.

Graph partitioning algorithms. To evaluate the performance of distributed graph algorithm, Ma et al. introduced three measures, which are visit times, makespan and data shipment. As efficiency (makespan) remains the dominant factor, they suggested to sacrifice visit times and data shipment for makespan, which advocates a well-balanced graph partition strategy when designing distributed algorithms. Actually, various graph partitioning algorithms focused on this object as well. METIS is an off-line graph partitioning package which can bring off high quality graph partitioning subject to a variety of requirements. But it is expensive to use METIS partitioning large graphs.

Disadvantages

·      The existing graph computation systems may suffer from the high-quality graph partition at a certain point.

·      Existing graph computation systems cannot efficiently exploit the benefit of high quality graph partitions. 

Proposed System

In this project, we present a novel graph computation engine, partition aware graph computation engine (PAGE). To efficiently support computation tasks with different partitioning qualities, we develop some unique components in this new framework. First, in PAGE’s worker, communication module is extended with a new dual concurrent message processor. The message processor concurrently handles both local and remote incoming messages in a unified way, thus accelerating the message processing. Furthermore, the concurrency of the message processor is tunable according to the online statistics of the system. Second, a partition aware module is added in each worker to monitor the partition related characters and adjust the concurrency of the message processor adaptively to fit the online workload.

The work of dynamic graph repartition and PAGE are orthogonal. To balance the workload, the proposed strategies repartition the graph according to the online workload. Thus the quality of underlying graph partition changes along with repartitioning. The existing graph computation systems may suffer from the high-quality graph partition at a certain point, but PAGE can mitigate this drawback and improve the performance by decreasing the cost of a worker further.

Advantages

·      PAGE can mitigate the drawback and improve the performance by decreasing the cost of a worker further.

·      To efficiently support computation tasks with different partitioning qualities, we develop some unique components in this new framework.

·      PAGE can effectively harness the partition information to guide parallel processing resource allocation, and improve the computation performance.

·      We introduce a dual concurrent message processor. The message processor concurrently processes incoming messages in a unified way and is the cornerstone in PAGE.

·      We present a dynamic concurrency control model. The model estimates concurrency for dual concurrent message processor by satisfying the producer consumer constraints. The model always generates proper configurations for PAGE when the graph applications or underlying graph partitions change.

System Architecture

SYSTEM CONFIGURATION

HARDWARE REQUIREMENTS:-

·       Processor                    -   Pentium –III

·      Speed            -    1.1 Ghz

·      RAM             -    256 MB(min)

·      Hard Disk              -   20 GB

·      Floppy Drive         -    1.44 MB

·      Key Board             -    Standard Windows Keyboard

·      Mouse           -    Two or Three Button Mouse

·      Monitor                 -    SVGA

SOFTWARE REQUIREMENTS:-

·      Operating System          : Windows  7                                  

·      Front End                      : JSP AND SERVLET

·      Database                       : MYSQL

References:

Yingxia Shao; Bin Cui; Lin Ma “PAGE: A PARTITION AWARE ENGINE FOR PARALLEL GRAPH COMPUTATION” Knowledge and Data Engineering, IEEE Transactions on May 2014.

Key-Recovery Attacks On Kids, A Keyed Anomaly Detection System

ABSTRACT:

Most anomaly detection systems rely on machine learning algorithms to derive a model of normality that is later used to detect suspicious events. Some works conducted over the last years have pointed out that such algorithms are generally susceptible to deception, notably in the form of attacks carefully constructed to evade detection. Various learning schemes have been proposed to overcome this weakness. One such system is KIDS (Keyed IDS), introduced at DIMVA’10. KIDS’ core idea is akin to the functioning of some cryptographic primitives, namely to introduce a secret element (the key) into the scheme so that some operations are infeasible without knowing it. In KIDS the learned model and the computation of the anomaly score are both key-dependent, a fact which presumably prevents an attacker from creating evasion attacks. In this work we show that recovering the key is extremely simple provided that the attacker can interact with KIDS and get feedback about probing requests. We present realistic attacks for two different adversarial settings and show that recovering the key requires only a small amount of queries, which indicates that KIDS does not meet the claimed security properties. We finally revisit KIDS’ central idea and provide heuristic arguments about its suitability and limitations.

AIM

The aims of this paper KIDS the learned model and the computation of the anomaly score are both key-dependent, a fact which presumably prevents an attacker from creating evasion attacks.

SCOPE

 The Scope of this project is show that recovering the key is extremely simple provided that the attacker can interact with KIDS and get feedback about probing requests.

EXISTING SYSTEM

Accurately pointed out that security problems differ from other application domains of machine learning in, at least, one fundamental feature: the presence of an adversary who can strategically play against the algorithm to accomplish his goals. Thus for example, one major objective for the attacker is to avoid detection. Evasion attacks exploit weaknesses in the underlying classifiers, which are often unable to identify a malicious sample that has been conveniently modified so as to look normal. Examples of such attacks abound. For instance, spammers regularly obfuscate their emails in various ways to avoid detection, e.g. by modifying words that are usually found in spam, or by including a large number of words that do not. Similarly malware and other pieces of attack code can be carefully adapted so as to evade Intrusion Detection Systems (IDS) without compromising the functionality of the attack

DISADVANTAGES:

1.  Anomaly  detection systems rely on machine learning algorithms to derive a model of normality that is later used to detect suspicious events
2. Such  algorithms are generally susceptible to deception, notably in the form of attacks carefully constructed to evade detection.

PROPOSED SYSTEM

KIDS (Keyed Intrusion Detection System) , introduced by Mrdovic and Drazenovic at DIMVA’10. KIDS is an application layer network anomaly detection system that extracts a number of features (“words”) from each payload. The system then builds a model of normality based both on the frequency of observed features and their relative positions in the payload. KIDS’ core idea to impede evasion attacks is to incorporate the notion of a “key”, this being a secret element used to determine how classification features are extracted from the payload. The security argument here is simple: even though the learning and testing algorithms are public, an adversary who is not in possession of the key will not know exactly how a request will be processed and, consequently, will not be able to design attacks that thwart detection

ADVANTAGES

1. It has been on recovering the key through efficient procedures, demonstrating that the classification process leaks information about it that can be leveraged by an attacker.
2. The  ultimate goal is to evade the system, and we have just assumed that knowing the key is essential to craft an attack that evades detection or, at least, that significantly facilitates the process

SYSTEM CONFIGURATION:-

HARDWARE REQUIREMENTS:-

1. Processor             -    Pentium –IV

2. Speed                   -   1.1 Ghz
3. RAM                    -   512 MB(min)
4. Hard Disk           -    40 GB
5. Key Board          -    Standard Windows Keyboard
6. Mouse                -    Two or Three Button Mouse
7. Monitor                      -    LCD/LED

 SOFTWARE REQUIREMENTS:

1. Operating System              : Windows 7             
2.  Front End                           : ASP.net and C#
3. Database                             : MSSQL
4. Tool                                    : Microsoft Visual studio

REFERENCE:

Tapiador, J.E, Orfila, A. ; Ribagorda, A. ; Ramos, B.. “Key-Recovery Attacks On Kids, A Keyed Anomaly Detection System”, IEEE Transactions on Dependable and Secure Computing, Volume 12  Issue 3  , SEPTEMBER 2013

Generating Searchable Public-Key Cipher texts with Hidden Structures for Fast Keyword Search

Abstract

Existing semantically secure public-key searchable encryption schemes take search time linear with the total number of the cipher texts. This makes retrieval from large-scale databases prohibitive. To alleviate this problem, this paper proposes Searchable Public-Key Ciphertexts with Hidden Structures (SPCHS) for keyword search as fast as possible without sacrificing semantic security of the encrypted keywords. In SPCHS, all keyword-searchable ciphertexts are structured by hidden relations, and with the search trapdoor corresponding to a keyword, the minimum information of the relations is disclosed to a search algorithm as the guidance to find all matching ciphertexts efficiently. We construct a SPCHS scheme from scratch in which the ciphertexts have a hidden star-like structure. We prove our scheme to be semantically secure in the Random Oracle (RO) model. The search complexity of our scheme is dependent on the actual number of the ciphertexts containing the queried keyword, rather than the number of all ciphertexts. Finally, we present a generic SPCHS construction from anonymous identity-based encryption and collision-free full-identity malleable Identity-Based Key Encapsulation Mechanism (IBKEM) with anonymity. We illustrate two collision-free full-identity malleable IBKEM instances, which are semantically secure and anonymous, respectively, in the RO and standard models. The latter instance enables us to construct an SPCHS scheme with semantic security in the standard model.

Aim

The aim is to generate Searchable Public-Key Ciphertexts with Hidden Structures (SPCHS) for keyword search as fast as possible without sacrificing semantic security of the encrypted keyword.

Scope

The scope is a generic SPCHS construction from anonymous identity-based encryption and collision-free full-identity malleable Identity-Based Key Encapsulation Mechanism (IBKEM) with anonymity.

Existing System

PUBLIC-KEY encryption with keyword search (PEKS), has the advantage that anyone who knows the receiver’s public key can upload keyword-searchable ciphertexts to a server. The receiver can delegate the keyword search to the server. More specifically, each sender separately encrypts a file and its extracted keywords and sends the resulting ciphertexts to a server; when the receiver wants to retrieve the files containing a specific keyword,  delegates a keyword search trapdoor to the server; the server finds the encrypted files containing the queried keyword without knowing the original files or the keyword itself, and returns the corresponding encrypted files to the receiver; finally, the receiver decrypts these encrypted files1. The authors of PEKS also presented semantic security against chosen keyword attacks (SSCKA) in the sense that the server cannot distinguish the ciphertexts of the keywords of its choice before observing the corresponding keyword search trapdoors. It seems an appropriate security notion, especially if the keyword space has no high min-entropy. Existing semantically secure PEKS schemes take search time linear with the total number of all ciphertexts. This makes retrieval from large-scale databases prohibitive. Therefore, more efficient search performance is crucial for practically deploying PEKS schemes. One of the prominent works to accelerate the search over encrypted keywords in the public-key setting is deterministic encryption. An encryption scheme is deterministic if the encryption algorithm is deterministic. Bellare et al. focuses on enabling search over encrypted keywords to be as efficient as the search for unencrypted keywords, such that a ciphertext containing a given keyword can be retrieved in time complexity logarithmic in the total number of all ciphertexts. This is reasonable because the encrypted keywords can form a tree-like structure when stored according to their binary values. However, deterministic encryption has two inherent limitations. First, keyword privacy can be guaranteed only for keywords that are a priori hardto- guess by the adversary (i.e., keywords with high minentropy to the adversary); second, certain information of a message leaks inevitably via the cipher text of the keywords since the encryption is deterministic. Hence, deterministic encryption is only applicable in special scenarios.

Disadvantages

Existing semantically secure public-key searchable encryption schemes take search time linear with the total number of the cipher texts. This makes retrieval from large-scale databases prohibitive.

Proposed System

Keyword searchable ciphertexts with their hidden structures can be generated in the public key setting; with a keyword search trapdoor, partial relations can be disclosed to guide the discovery of all matching ciphertexts. Semantic security is defined for both the keywords and the hidden structures. It is worth noting that this new concept and its semantic security are suitable for keyword-searchable ciphertexts with any kind of hidden structures. In contrast, the concept of traditional PEKS does not contain any hidden structure among the PEKS ciphertexts; correspondingly, its semantic security is only defined for the keywords. Following the SPCHS definition, we construct a simple SPCHS from scratch in the random oracle (RO) model. The scheme generates keyword-searchable ciphertexts with a hidden star-like structure. The search performance mainly depends on the actual number of the ciphertexts containing the queried keyword. For security, the scheme is proven semantically secure based on the Decisional Bilinear Diffie- Hellman (DBDH) assumption in the RO model. We are also interested in providing a generic SPCHS construction to generate keyword-searchable ciphertexts with a hidden star-like structure. Our generic SPCHS is inspired by several interesting observations on Identity-Based Key Encapsulation Mechanism (IBKEM). In IBKEM, a sender encapsulates a key K to an intended receiver ID. Of course, receiver ID can decapsulate and obtain K, and the sender knows that receiver ID will obtain K. However, a non-intended receiver ID0 may also try to decapsulate and obtain K0. We observe that, (1) it is usually the case that K and K0 are independent of each other from the view of the receivers, and (2) in some IBKEM the sender may also know K0 obtained by receiver ID0. We refer to the former property as collision freeness and to the latter as full-identity malleability. An IBKEM scheme is said to be collision-free full-identity malleable if it possesses both properties. We transform this IBE scheme into a collision-free full-identity malleable IBKEM scheme with semantic security and anonymity in the standard model. Hence, this new IBKEM scheme allows us to build SPCHS schemes secure in the standard model with the same search performance as the previous SPCHS construction from scratch in the RO model.

Advantages

·      It outperforms existing PEKS schemes with semantic security, whose search complexity is linear with the number of all ciphertexts.
·      We identified several interesting properties, i.e., collision-freeness and full-identity malleability in some IBKEM instances, and formalized these properties to build a generic SPCHS construction.
·      SPCHS seems a promising tool to solve some challenging problems in public-key searchable encryption. One application may be to achieve retrieval completeness verification which, to the best of our knowledge, has not been achieved in existing PEKS schemes.
·      Specifically, by forming a hidden ring-like structure, i.e., letting the last hidden pointer always point to the head, one can obtain PEKS allowing to check the completeness of the retrieved ciphertexts by checking whether the pointers of the returned ciphertexts form a ring.

System Specification

Hardware Requirements

• Speed                  -    1.1 Ghz
• Processor              -    Pentium IV
• RAM                    -    512 MB (min)
• Hard Disk            -    40 GB
• Key Board                    -    Standard Windows Keyboard
• Mouse                  -    Two or Three Button Mouse
• Monitor                -     LCD/LED

 Software requirements

• Operating System              : Windows 7             
•  Front End                           : ASP.Net and C#
• Database                             : MSSQL
• Tool                                    : Microsoft Visual studio

References:

Wu, Q.; Wang, W.; Susilo, W. Xu, P. " GENERATING SEARCHABLE PUBLIC-KEY CIPHERTEXTS WITH HIDDEN STRUCTURES FOR FAST KEYWORD SEARCH", IEEE Transactions on Information Forensics and Security Volume:10 , Issue: 9 , June 2015

A Trust-based Privacy-Preserving Friend Recommendation Scheme for Online Social Networks

ABSTRACT

Online Social Networks (OSNs), which attract thousands of million people to use everyday, greatly extend OSN users’ social circles by friend recommendations. OSN users’ existing social relationship can be characterized as 1-hop trust relationship, and further establish a multi-hop trust chain during the recommendation process. As the same as what people usually experience in the daily life, the social relationship in cyberspaces are potentially formed by OSN users’ shared attributes, e.g., colleagues, family members, or classmates, which indicates the attribute-based recommendation process would lead to more fine-grained social relationships between strangers. Unfortunately, privacy concerns raised in the recommendation process impede the expansion of OSN users’ friend circle. Some OSN users refuse to disclose their identities and their friends’ information to the public domain. In this paper, we propose a trust based privacy-preserving friend recommendation scheme for OSNs, where OSN users apply their attributes to find matched friends, and establish social relationships with strangers via a multi-hop trust chain. Based on trace-driven experimental results and security analysis, we have shown the feasibility and privacy preservation of our proposed scheme.

AIM

The aim of this paper is OSN users apply their attributes to find matched friends, and establish social relationships with strangers via a multi-hop trust chain

SCOPE:

The Scope of this Paper is to trace-driven experimental results and security analysis, we have shown the feasibility and privacy preservation of our Trust Based Privacy Preserving Friend Recommendation Scheme.

EXISTING SYSTEM

On the one hand, directly asking recommendations to strangers or a non close friend not only reveals Alice’s identity, but also reveals her health condition and medical information. Even worse, traditional recommendation approaches applying identity to recommend strangers will disclose OSN users’ social relationships to the public, which impede patients from utilizing it, and also decrease the possibility of establishing the multi-hop trust chain if one of OSN users on the chain returns a negative result. On the other hand, current approaches cannot achieve the fine-grained and context-aware results automatically, due to the fact that OSN users have to determine the recommended friends based on their own judgments on the recommendation query. As in our example, Alice would like to ask for help from her friends who work in a hospital, but not a truck driver. To overcome the above issue, we consider the possibility of singsong users’ social attributes to establish the multi-hop trust chain based on each context-aware 1-hop trust relationship, where most of trust relationships are formed and strengthened by the shared social attributes.

DISADVANTAGES

1. Privacy  concerns raised in the recommendation process impede the expansion of OSN users’ friend circle
2. Some OSN users refuse to disclose their identities and their friend’s information to the public domain.

PROPOSED SYSTEM

In this paper, design a light-weighted privacy-preserving friend recommendation scheme for OSNs by utilizing both users’ social attributes and their existing trust relationships to establish a multi-hop trust chain between strangers. In our scheme, we jointly consider privacy leakages and preservation approaches regarding the identity, social attributes, and their trust relationships of OSN users during the recommendation process. By trace-driven experimental results, we demonstrate both the security and efficiency of our proposed scheme

ADVANTAGES

1. Based on the 1-hop trust relationships, we extend existing friendships to multi-hop trust chains without compromising recommenders identity privacy
2. Extensive trace-driven experiment are deployed to verify the performance of our scheme in terms of security, efficiency, and feasibility.

 SYSTEM ARCHITECTURE

 

 

SYSTEM CONFIGURATION:-

Hardware Requirements

• Speed                  -    1.1 Ghz
• Processor              -    Pentium IV
• RAM                    -    512 MB (min)
• Hard Disk            -    40 GB
• Key Board                    -    Standard Windows Keyboard
• Mouse                  -    Two or Three Button Mouse
• Monitor                -     LCD/LED

 Software requirements

• Operating System              : Windows 7             
•  Front End                           : ASP.Net and C#
• Database                             : MSSQL
• Tool                                    : Microsoft Visual studio

REFERENCE

Zhang, C Fang, Y.Guo, L.“ A Trust-based Privacy-Preserving Friend Recommendation Scheme for Online Social Networks,” IEEE Transactions on Dependable and Secure Computing, Volume 12 ,  Issue 4  , SEPTEMBER 2014.