With the steady growth of Android malware, we suspect that, during the malware development phase, some Android malware writers use the popular public scanning services (e.g., VirusTotal) for testing the evasion capability of their malware samples, which we name Android malware development cases (AMDs). In this work, we design an AMD hunter in the context of VirusTotal to hunt for AMDs and reveal new threats for Android. First, the AMD hunter sifts through millions of file submissions on VirusTotal efficiently and alert more suspicious submission traces. Second, it performs package level analysis, static code and dynamic analyses on the APKs of the suspicious submissions to validate the AMDs. The implemented hunter has been used in a leading security company for 4 months, which processed 153 million of submissions on VirusTotal, and identified 1,623 AMDs with 13,855 samples from 83 countries. We also performed case studies on 890 malware samples selected from the identified AMDs, which revealed lots of new threats, including the development cases of fake system/banking phishing app, new rooting exploits, new JavaScript based threats, new evasions and AV probing malware. We wrote industry research articles about some AMDs and notified other security vendors to help patch their false negatives. Besides raising the awareness of the existence of AMDs, more importantly, our research provides the first systematic and efficient way to study the malware development phenomenon on VirusTotal. We will share all the samples of the identified AMDs with the research community.

User's digital identity information has privacy and security requirements. Privacy requirements include confidentiality of the identity information itself, anonymity of those who verify and consume a user's identity information and unlinkability of online transactions which involve a user's identity. Security requirements include correctness, ownership assurance and prevention of counterfeits of a user's identity information. Such privacy and security requirements, although conflicting, are critical for identity management systems enabling the exchange of users' identity information between different parties during the execution of online transactions. Addressing all such requirements, without a centralized party managing the identity exchange transactions, raises several challenges. This paper presents a decentralized protocol for privacy preserving exchange of users' identity information addressing such challenges. The proposed protocol leverages advances in blockchain and zero knowledge proof technologies, as the main building blocks. We provide prototype implementations of the main building blocks of the protocol and assess its performance and security.

Tensor decomposition methods are effective tools for modelling multidimensional array data (i.e., tensors). Among them, nonparametric Bayesian models, such as Infinite Tucker Decomposition (InfTucker), are more powerful than multilinear factorization approaches, including Tucker and PARAFAC, and usually achieve better predictive performance. However, they are difficult to handle massive data due to a prohibitively high training cost. To address this limitation, we propose Distributed infinite Tucker (DinTucker), a new hierarchical Bayesian model that enables local learning of InfTucker on subarrays and global information integration from local results. We further develop a distributed stochastic gradient descent algorithm, coupled with variational inference for model estimation. In addition, the connection between DinTucker and InfTucker is revealed in terms of model evidence. Experiments demonstrate that DinTucker maintains the predictive accuracy of InfTucker and is scalable on massive data: On multidimensional arrays with billions of elements from two real-world applications, DinTucker achieves significantly higher prediction accuracy with less training time, compared with the state-of-the-art large-scale tensor decomposition method, GigaTensor.

Android malware scanning services (e.g., VirusTotal) are websites that users submit suspicious Android programs and get an array of malware detection results. With the growing popularity of such websites, we suspect that, these services are not only used by innocent users, but also, malware writers for testing the evasion capability of their malware samples. May this hypothesis be true, it not only provides interesting insight on Android malware development (AMD), but also provides opportunities for important security applications such as zero-day sample detection. In this work, we first validate this hypothesis with massive data; then design a system AMDHunter to hunt for AMDs on VirusTotal that reveals new threats for Android that has never been revealed before. This is the first systematic study of the malware development phenomenon on VirusTotal, and the first system to automatically detect such malware development cases. AMDHunter has been used in a leading security company for months. Our study is driven by the large amount of data on VirusTotal- We analyzed 153 million submissions collected on VirusTotal during 102 days. Our system identifies 1,623 AMDs with 13,855 samples from 83 countries. We also performed case studies on 890 malware samples selected from the identified AMDs, which revealed lots of new threats, e.g., the development cases of fake system/banking phishing malware, new rooting exploits and etc.

Firewall policies are notorious for having misconfiguration errors which can defeat its intended purpose of protecting hosts in the network from malicious users. We believe this is because today's firewall policies are mostly monolithic. Inspired by ideas from modular programming and code refactoring, in this work we introduce three kinds of modules: primary, auxiliary, and template, which facilitate the refactoring of a firewall policy into smaller, reusable, comprehensible, and more manageable components. We present algorithms for generating each of the three modules for a given legacy firewall policy. We also develop ModFP, an automated tool for converting legacy firewall policies represented in access control list to their modularized format. With the help of ModFP, when examining several real-world policies with sizes ranging from dozens to hundreds of rules, we were able to identify subtle errors.

Relying on an access control security policy alone to protect valuable resources is a dangerous practice. Prudent security must engage in other risk management and mitigation techniques to rapidly detect and recover from breaches. In reality, many security policies are either wrong, containing errors, or are misused and abused by malicious employees or compromised accounts; not all granted access is desirable. A popular approach to mitigate against these and other residual threats is to monitor applications to detect misuse and abuse of credentials in near real-time.

Organizations rarely define formal security properties or policies for their access control systems, often choosing to react to changing needs. This paper addresses the problem of reconciling entitlement usage with configured policies for multiple objectives: policy optimization and risk mitigation. Policies should remain up-to-date, maintaining least privilege, and using unambiguous constructs that reduce administrative stress.

This paper describes our system, built as part of a commercially available product, for inferring the risk in an RBAC policy model, i.e., the assignment of permissions to roles and roles to users. Our system implements a general model of risk based on any arbitrary set of properties of permissions and users. Our experience shows that fuzzy inferencing systems are best suited to capture how humans assign risk to such assignments. To implement fuzzy inferencing practically we need the axiom of monotonicity, i.e., risk can not decrease when more permissions are assigned to a role or when the role is assigned to fewer users. We describe the visualization component which administrators can use to infer aggregate risk in role assignments as well as drill down into which assignments are actually risky. Administrators can then use this knowledge to refactor roles and assignments.

We consider a fundamentally new approach to role and policy mining: finding RBAC models which reflect the observed usage of entitlements and the attributes of users. Such policies are interpretable, i.e., there is a natural explanation of why a role is assigned to a user and are conservative from a security standpoint since they are based on actual usage. Further, such "generative" models provide many other benefits including reconciliation with policies based on entitlements, detection of provisioning errors, as well as the detection of anomalous behavior. Our contributions include defining the fundamental problem as extensions of the well-known role mining problem, as well as providing several new algorithms based on generative machine learning models. Our algorithms find models which are causally associated with actual usage of entitlements and any arbitrary combination of user attributes when such information is available. This is the most natural process to provision roles, thus addressing a key usability issue with existing role mining algorithms.

The Enterprise Information Security Management (EISM) system aims to semi-automatically estimate the sensitivity of enterprise data through advanced content analysis and business process mining. We demonstrate a proof-of-concept of EISM that crawls all the files in a personal computer and estimates the sensitivity of individual files and the overall sensitivity level of the computer. The system can identify 11 different personally identifiable information (PII) types and 11 sensitive data categories, and estimate data sensitivity based on the identified sensitive information in the data. Furthermore, the tool produces the evidences of the discovered sensitive information including the surrounding context in the document to help users understand what kinds of sensitive information are stored in their computer. The evidences allow users can easily redact the sensitive information or move it to a more secure location. Thus, this system can be used as a privacy enhancing tool as well as a security tool.

Mashup applications mix and merge content (data and code) from multiple content providers in a user's browser, to provide high-value web applications that can rival the user experience provided by desktop applications. Current browser security models were not designed to support such applications and they are therefore implemented with insecure workarounds. In this paper, we present a secure component model, where components are provided by different trust domains, and can interact using a communication abstraction that allows ease of specification of a security policy. We have developed an implementation of this model that works currently in all major browsers, and addresses challenges of communication integrity and frame-phishing. An evaluation of the performance of our implementation shows that this approach is not just feasible but also practical.

In this paper, we develop two mechanisms to detect DoS attacks against CDN-hosted Web sites and CDN infrastructure servers. First, we propose a novel request routing algorithm which allows CDN servers to effectively distinguish attacks from legitimate requests. Our scheme, based on a keyed hash function, significantly improves the resilience of servers to DoS attacks. Second, we introduce several site allocation algorithms based on binary codes which insure that an attack on one hosted Web site has a limited impact on other hosted sites. Our scheme guarantees that a specified minimum number of servers remain available for non-victimized sites. Together, the proposed schemes significantly improve the resilience of CDN-hosted Web sites, and complement other work on countering distributed DoS attacks.

Detecting attacks against systems has, in practice, largely been delegated to sensors, such as network intrustion detection systems. However, due to the inherent limitations of these systems and the increasing use of encryption in communication, intrusion detection and prevention have once again moved back to the host systems themselves. In this paper, we describe our experiences with building BlueBox, a host-based intrusion detection system. Our approach, based on the technique of system call introspection, can be viewed as creating an infrastructure for defining and enforcing very fine-grained process capabilities in the kernel. These capabilities are specified as a set of rules (policies) for regulating access to system resources on a per executable basis. The language for expressing the rules is intuitive and sufficiently expressive to effectively capture security boundaries.We have prototyped our approach on Linux operating system kernel and have built rule templates for popular daemons such as Apache and wu-ftpd. Our design has been validated by testing against a comprehensive database of known attacks. Our system has been designed to minimize the kernel changes and performance impact and thus can be ported easily to new kernels. We describe the motivation and rationale behind BlueBox, its design, implementation on Linux, and how it relates to prior work on detecting and preventing intrusions on host systems.

In this paper, we study the notion of completeness under random reductions and explore how that depends on the type and success probability of the reduction. We obtain absolute separations between completeness notions under various random reductions and between random reductions and deterministic reductions. These separations are obtained in appropriately high complexity classes where these questions do not have contradictory relativizations. Our results show that the notion of completeness under random reductions is sensitive tovery smallchanges in success probability, since we can separate completeness under reductions with very small differ- ences in success probability. We also obtain optimal separations between completeness under various deterministic reductions and random reductions.

In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the $RNC$ algorithm for perfect matching by Mulmuley, Vazirani, and Vazirani [Combinatorica, 7 (1987), pp. 105–113] and in several other applications. Given a set S and an unknown family $\mathcal{F} \subseteq 2^{S}$ with $|\mathcal{F}| \leq Z$, we present a scheme for assigning polynomially bounded weights to the elements of S using only $O(\log Z + \log |S|)$ random bits, such that the minimum weight set in $\mathcal{F}$ is unique with high probability. This generalizes the solution of Mulmuley, Vazirani, and Vazirani, who use $O(S \log S)$ bits, independent of Z. We also provide a matching lower bound for the randomness complexity of this problem. The new weight assignment scheme yields a randomness-efficient $RNC^{2}$ algorithm for perfect matching which uses $O(\log Z + \log n)$ random bits, where Z is any given upper bound on the number of perfect matchings in the input graph. This generalizes the result of Grigoriev and Karpinski [Proc. IEEE Symposium on Foundations of computer Science, 1987, pp. 166–172], who present an $NC^{3}$ algorithm when Z is polynomial and improves the running time in this case. The worst-case randomness complexity of our algorithm is $O(n \log (m/n))$ random bits improving on the previous bound of $O(m \log n)$. Our scheme also gives randomness-efficient solutions for several problems where unique element isolation is used, such as $RNC$ algorithms for variants of matching and basic problems on linear matroids. We obtain a randomness-efficient random reduction from SAT to USAT, the language of uniquely satisfiable formulas, which can be derandomized in the case of languages in Few P to yield new proofs of the results Few $P \subseteq \oplus P$ and Few $P \subseteq C_{=} P$.

Article Improved algorithms via approximations of probability distributions (extended abstract) Share on Authors: Suresh Chari Dept. of Computer Science, Cornell University, Ithaca NY Dept. of Computer Science, Cornell University, Ithaca NYView Profile , Pankaj Rohatgi Thompson Consumer Electronics, Los Angeles, CA Thompson Consumer Electronics, Los Angeles, CAView Profile , Aravind Srinivasan DIMACS Center, Rutgers University, Piscataway, NJ, and School of Mathematics, The Institute for Advanced Study, Princeton, NJ DIMACS Center, Rutgers University, Piscataway, NJ, and School of Mathematics, The Institute for Advanced Study, Princeton, NJView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 584–592https://doi.org/10.1145/195058.195411Published:23 May 1994 9citation251DownloadsMetricsTotal Citations9Total Downloads251Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the RNC algorithm for perfect matching due to Mulmuleg, Va.zirani @ Vazirani and in several other applications.Given a set S and an unknown family F ~2s with \F~< Z, we present a scheme to assign polynomially bounded weights to the elements of S using onlg O(log Z + log ISI) random bits, such that the minimum weight set in F is unique with high probability.This generalizes and improves the results of Mulmuley, Vazirani & Va.zirani who give a scheme which uses 0(S log S) random bits independent of Z.We also prove a matching lower bound for the randomness complezitp of this problem.OUT generalization gives a randomness-e ficient RNC2 algorithm for perfect matching which uses O(log Z -t-log n) random bits where Z is any given upper bound on the number of perfect matchings in the given graph.This improves and generalizes the results of Grigoriev & Karpinski who present an NC3 algorithm when Z is polynomially bounded.The