15799228
Security policy reconciliation in distributed computing environments
A major hurdle in sharing resources between organizations is heterogeneity. Therefore, in order for two organizations to collaborate their policies have to be resolved. The process of resolving different policies is known as policy reconciliation, which in general is an intractable problem. This paper addresses policy reconciliation in the context of security. We present a formal framework and hierarchical representation for security policies. Our hierarchical representation exposes the structure of the policies and leads to an efficient reconciliation algorithm. We also demonstrate that agent preferences for security mechanisms can be readily incorporated into our framework. We have implemented our reconciliation algorithm in a library called the policy reconciliation engine or PRE. In order to test the implementation and measure the overhead of our reconciliation algorithm, we have integrated PRE into a distributed high-throughput system called Condor.
12292877
Weighted Pushdown Systems and Trust-Management Systems
The authorization problem is to decide whether, according to a security policy, some principal should be allowed access to a resource. In the trust-management system SPKI/SDSI, the security policy is given by a set of certificates, and proofs of authorization take the form of certificate chains. The certificate-chain-discovery problem is to discover a proof of authorization for a given request. Certificate-chain-discovery algorithms for SPKI/SDSI have been investigated by several researchers. We consider a variant of the certificate-chain discovery problem where the certificates are distributed over a number of servers, which then have to cooperate to identify the proof of authorization for a given request. We propose two protocols for this purpose. These protocols are based on distributed model-checking algorithms for weighted pushdown systems (WPDSs). These protocols can also handle cases where certificates are labeled with weights and where multiple certificate chains must be combined to form a proof of authorization. We have implemented these protocols in a prototype and report preliminary results of our evaluation.
3839837
Creating Vulnerability Signatures Using Weakest Preconditions
Signature-based tools such as network intrusion detection systems are widely used to protect critical systems. Automatic signature generation techniques are needed to enable these tools due to the speed at which new vulnerabilities are discovered. In particular, we need automatic techniques which generate sound signatures - signatures which will not mistakenly block legitimate traffic or raise false alarms. In addition, we need signatures to have few false negatives and will catch many different exploit variants. We investigate new techniques for automatically generating sound vulnerability signatures with fewer false negatives than previous research using program binary analysis. The key problem to reducing false negatives is to consider as many as possible different program paths an exploit may take. Previous work considered each possible program path an exploit may take separately, thus generating signatures that are exponential in the size of the number of branches considered. In the exact same scenario, we show how to reduce the overall signature size and the generation time from exponential to polynomial. We do this without requiring any additional assumptions, or relaxing any properties. This efficiency gain allows us to consider many more program paths, which results in reducing the false negatives of generated signatures. We achieve these results by creating algorithms for generating vulnerability signatures that are based on computing weakest preconditions (WP). The weakest precondition for a program path to a vulnerability is a function which matches all exploits that may exploit the vulnerability along that path. We have implemented our techniques and generated signatures for several binary programs. Our results demonstrate that our WP-based algorithm generates more succinct signatures than previous approaches which were based on forward symbolic execution.
796248
An auctioning reputation system based on anomaly
Existing reputation systems used by online auction houses do not address the concern of a buyer shopping for commodities - finding a good bargain. These systems do not provide information on the practices adopted by sellers to ensure profitable auctions. These practices may be legitimate, like imposing a minimum starting bid on an auction, or fraudulent, like using colluding bidders to inflate the final price in a practice known as shilling.We develop a reputation system to help buyers identify sellers whose auctions seem price-inflated. Our reputation system is based upon models that characterize sellers according to statistical metrics related to price inflation. We combine the statistical models with anomaly detection techniques to identify the set of suspicious sellers. The output of our reputation system is a set of values for each seller representing the confidence with which the system can say that the auctions of the seller are price-inflated.We evaluate our reputation system on 604 high-volume sellers who posted 37,525 auctions on eBay. Our system automatically pinpoints sellers whose auctions contain potential shill bidders. When we manually analyze these sellers' auctions, we find that many winning bids are at about the items' market values, thus undercutting a buyer's ability to find a bargain and demonstrating the effectiveness of our reputation system.
7290502
Towards automatic generation of vulnerability-based signatures
In this paper we explore the problem of creating vulnerability signatures. A vulnerability signature matches all exploits of a given vulnerability, even polymorphic or metamorphic variants. Our work departs from previous approaches by focusing on the semantics of the program and vulnerability exercised by a sample exploit instead of the semantics or syntax of the exploit itself. We show the semantics of a vulnerability define a language which contains all and only those inputs that exploit the vulnerability. A vulnerability signature is a representation (e.g., a regular expression) of the vulnerability language. Unlike exploit-based signatures whose error rate can only be empirically measured for known test cases, the quality of a vulnerability signature can be formally quantified for all possible inputs. We provide a formal definition of a vulnerability signature and investigate the computational complexity of creating and matching vulnerability signatures. We also systematically explore the design space of vulnerability signatures. We identify three central issues in vulnerability-signature creation: how a vulnerability signature represents the set of inputs that may exercise a vulnerability, the vulnerability coverage (i.e., number of vulnerable program paths) that is subject to our analysis during signature creation, and how a vulnerability signature is then created for a given representation and coverage. We propose new data-flow analysis and novel adoption of existing techniques such as constraint solving for automatically generating vulnerability signatures. We have built a prototype system to test our techniques. Our experiments show that we can automatically generate a vulnerability signature using a single exploit which is of much higher quality than previous exploit-based signatures. In addition, our techniques have several other security applications, and thus may be of independent interest
5961776
NetSpy: Automatic Generation of Spyware Signatures for NIDS
We present NetSpy, a tool to automatically generate network-level signatures for spyware. NetSpy determines whether an untrusted program is spyware by correlating user input with network traffic generated by the untrusted program. If classified as spyware, NetSpy also generates a signature characterizing the malicious substrate of the spyware's network behavior. Such a signature can be used by network intrusion detection systems to detect spyware installations in large networks. In our experiments, NetSpy precisely identified each of the 7 spyware programs that we considered and generated network-level signatures for them. Of the 9 supposedly-benign programs that we considered, NetSpy correctly characterized 6 of them as benign. The remaining 3 programs showed network behavior that was highly suggestive of spying activity
26896458
The Axiomatization of Arithmetic
15968114
An Efficient Explicit-time Description Method for Timed Model Checking
Timed modelchecking,the methodtoformallyverifyreal-timesystems, is attractingincreasingatten-tion from both the model checking community and the real-time community. Explicit-time descrip-tion methods verify real-time systems using general model constructs found in standard un-timedmodel checkers. Lamport proposed an explicit-time description method [17] using a clock-tickingprocess (Tick) to simulate the passage of time together with a group of global variables to model timerequirements. Two methods, the Sync-based Explicit-time Description Methodusing rendezvoussynchronization steps and the Semaphore-based Explicit-time Description Methodusing only oneglobal variable were proposed [27, 26]; they both achieve better modularity than Lamport’s methodin modelingthe real-time systems. In contrast to timed automatabased model checkerslike UPPAAL[7], explicit-time description methods can access and store the current time instant for future calcula-tions necessary for many real-time systems, especially those with pre-emptive scheduling. However,the Tick process in the above three methods increments the time by one unit in each tick; the statespaces therefore grow relatively fast as the time parameters increase, a problem when the system’stime period is relatively long. In this paper, we propose a more efﬁcient method which enables theTick process to leap multiple time units in one tick. Preliminary experimentalresults in a high perfor-mance computing environment show that this new method signiﬁcantly reduces the state space andimproves both the time and memory efﬁciency.
14004456
Enhancing multimedia streaming performance through peer-paired collaboration
In this paper, a novel multimedia streaming framework called peer-paired pyramid streaming (P/sup 3/S) is proposed. The philosophy of P/sup 3/S is to enable collaboration between clients so as to bring in better performance. The structure of P/sup 3/S is basically a hybrid client/server and peer-to-peer structure and exhibits a triangle-cell based hierarchy. Based on P/sup 3/S, performance enhancement techniques are designed to increase the aggregated bandwidth of all participants. We present an optimal data allocation algorithm, which maximizes the overall throughput of the whole streaming session. We also present a greedy data allocation algorithm that is slightly suboptimal but much simpler. Extensive simulations were performed to demonstrate the effectiveness of proposed techniques.
31706841
A Fast Subspace Clustering Algorithm Based on Pattern Similarity
Traditional clustering models define similarity by distance over dimensions. However, distance functions are not always adequate in capturing correlations among the objects. Pattern-based clustering can discover this kind of clusters. But state-of-the-art pattern-based clustering methods are inefficient and haven't criteria to evaluate the quality of clusters. This paper presents a novel pattern similarity-based subspace clustering with the pattern tree (PPSC for short) that offers these capabilities. The method uses new evaluation criteria to discover best clusters, which enables user to find clusters according to different needs. Meanwhile, observing the analogy between mining frequent itemsets and discovering subspace clusters around random points, we apply the pattern-tree to determine subspace by scanning the database once, so it can perform efficiently in large datasets.
16868039
Automatic text discovering through stroke-based segmentation and text string combination
In this paper we present a novel framework of automatic text discovering for content-based multimedia application. For single image, the stroke-based binarization and the coarse-to-fine text extraction will collaborate to generate a clean text image for recognition. For image sequence, multi-frame text enhancement is adopted to increase the text/background contrast, and the recognition results are finally refined by the text string combination algorithm to get more precise semantic information. Two prototype demos have been successfully developed on mobile phones. The experimental results on different platforms show the superior performance of the proposed method.