Comprehensive Java Metadata Tracking for Attack Detection and Repair

Comprehensive Java Metadata Tracking for Attack Detection and Repair Perkins, Jeff; Eikenberry, Jordan; Coglio, Alessandro; Rinard, Martin We present ClearTrack, a system that tracks 32 bits of metadata for each primitive value in Java programs to detect and nullify a range of vulnerabilities such as integer overflow and underflow vulnerabilities, SQL injection vulnerabilities, and command injection vulnerabilities. Contributions include new techniques for eliminating false positives associated with benign integer overflows and underflows, new metadata-aware techniques for detecting and nullifying SQL and command injection attacks, and results from an evaluation of ClearTrack performed by a Test and Evaluation team hired by the sponsor of this research (an anonymous agency of the United States government). These results show that 1) ClearTrack operates successfully on Java programs comprising hundreds of thousands of lines of code (including instrumented jar files and Java system libraries, the majority of the applications comprise over 3 million lines of code), 2) because of computations such as cryptography and hash table calculations, these applications perform millions of benign integer overflows and underflows, and 3) ClearTrack successfully detects and nullifies all tested integer overflow and underflow, SQL injection, and command injection vulnerabilities in the benchmark applications.

from Computer Science and Artificial Intelligence Lab (CSAIL) https://ift.tt/359KcRk

Precise and Comprehensive Provenance Tracking for Android Devices

Precise and Comprehensive Provenance Tracking for Android Devices Gordon, Michael; Eikenberry, Jordan; Eden, Anthony; Perkins, Jeff; Rinard, Martin Detailed information about the paths that data take through a system is invaluable for understanding sources and behaviors of complex exfiltration malware. We present a new system, ClearScope, that tracks, at the level of individual bytes, the complete paths that data follow through Android systems. These paths include the original source where data entered the device (such as sensors or network connections), files in which the data was temporarily stored, applications that the data traversed during its time in the device, and sinks through which the data left the device. The ClearScope system design enables this unprecedented level of provenance tracking detail by 1) structuring the provenance representation as references, via provenance tags, to provenance events that record the movement of data between system components and into or out of the device and 2) adopting a split design in which provenance events are streamed to a remote server for storage, with only the minimal information required to generate the tagged stream of events retained on the device. ClearScope also includes compiler optimizations that enable efficient provenance tracking within applications by eliminating unnecessary provenance tracking computations and adopting and efficient aggregate provenance representation for arrays when all array elements have the same provenance. Experience using ClearScope to analyze the notorious Adups FOTA malware highlights the significant benefits that this level of comprehensive detail can bring. Performance experiments with the Caffeine Mark benchmarks show that the overall ClearScope provenance tracking overhead on this benchmark suite is 14%.

from Computer Science and Artificial Intelligence Lab (CSAIL) https://ift.tt/32XIFfv

Automatic Exploitation of Fully Randomized Executables

Automatic Exploitation of Fully Randomized Executables Gadient, Austin; Ortiz, Baltazar; Barrato, Ricardo; Davis, Eli; Perkins, Jeff; Rinard, Martin We present Marten, a new end to end system for automatically discovering, exploiting, and combining information leakage and buffer overflow vulnerabilities to derandomize and exploit remote, fully randomized processes. Results from two case studies high- light Marten’s ability to generate short, robust ROP chain exploits that bypass address space layout randomization and other modern defenses to download and execute injected code selected by an attacker. We present an automated system, Marten, that automatically generates control flow hijacking exploits against fully randomized executables by combining information leakage and buffer overflow exploits.

from Computer Science and Artificial Intelligence Lab (CSAIL) http://bit.ly/2MFt55i

Gen: A General-Purpose Probabilistic Programming System with Programmable Inference

Gen: A General-Purpose Probabilistic Programming System with Programmable Inference Cusumano-Towner, Marco F.; Lew, Alexander; Saad, Feras A.; Mansinghka, Vikash K. Probabilistic modeling and inference are central to many fields. A key challenge for wider adoption of probabilistic programming languages is designing systems that are both flexible and performant. This paper introduces Gen, a new probabilistic programming system with novel language con- structs for modeling and for end-user customization and optimization of inference. Gen makes it practical to write probabilistic programs that solve problems from multiple fields. Gen programs can combine generative models written in Julia, neural networks written in TensorFlow, and custom inference algorithms based on an extensible library of Monte Carlo and numerical optimization techniques. This paper also presents techniques that enable Gen’s combination of flexibility and performance: (i) the generative function inter- face, an abstraction for encapsulating probabilistic and/or differentiable computations; (ii) domain-specific languages with custom compilers that strike different flexibility/per- formance tradeoffs; (iii) combinators that encode common patterns of conditional independence and repeated compu- tation, enabling speedups from caching; and (iv) a standard inference library that supports custom proposal distributions also written as programs in Gen. This paper shows that Gen outperforms state-of-the-art probabilistic programming systems, sometimes by multiple orders of magnitude, on problems such as nonlinear state-space modeling, structure learning for real-world time series data, robust regression, and 3D body pose estimation from depth images.

from Computer Science and Artificial Intelligence Lab (CSAIL) https://ift.tt/2BxUoa6

Towards Understanding Generalization via Analytical Learning Theory

Towards Understanding Generalization via Analytical Learning Theory Kawaguchi, Kenji; Benigo, Yoshua; Verma, Vikas; Kaelbling, Leslie Pack This paper introduces a novel measure-theoretic theory for machine learning that does not require statistical assumptions. Based on this theory, a new regularization method in deep learning is derived and shown to outperform previous methods in CIFAR-10, CIFAR-100, and SVHN. Moreover, the proposed theory provides a theoretical basis for a family of practically successful regularization methods in deep learning. We discuss several consequences of our results on one-shot learning, representation learning, deep learning, and curriculum learning. Unlike statistical learning theory, the proposed learning theory analyzes each problem instance individually via measure theory, rather than a set of problem instances via statistics. As a result, it provides different types of results and insights when compared to statistical learning theory.

from Computer Science and Artificial Intelligence Lab (CSAIL) https://ift.tt/2IA13CS

Using Dynamic Monitoring to Synthesize Models of Applications That Access Databases

Using Dynamic Monitoring to Synthesize Models of Applications That Access Databases Shen, Jiasi; Rinard, MArtin We previously developed Konure, a tool that uses active learning to infer the functionality of database applications. An alternative approach is to observe the inputs, outputs, and database traffic from a running system in normal use and then synthesize a model of the application from this information. To evaluate these two approaches, we present Etch, which uses information from typical usage scenarios to synthesize a model of the functionality of database applications whose computation can be expressed in the Konure DSL.

from Computer Science and Artificial Intelligence Lab (CSAIL) https://ift.tt/2zDuMrp

Using Active Learning to Synthesize Models of Applications That Access Databases

Using Active Learning to Synthesize Models of Applications That Access Databases Shen, Jiasi; Rinard, Martin We present a new technique that uses active learning to infer models of applications that manipulate relational databases. This technique comprises a domain-specific language for modeling applications that access databases (each model is a program in this language) and an associated inference algorithm that infers models of applications whose behavior can be expressed in this language. The inference algorithm generates test inputs and database configurations, runs the application, then observes the resulting database traffic and outputs to progressively refine its current model hypothesis. The end result is a model that completely captures the behavior of the application. Because the technique works only with the externally observable inputs, outputs, and databases, it can infer the behavior of applications written in arbitrary languages using arbitrary coding styles (as long as the behavior of the application is expressible in the domain-specific language). We also present a technique for automatically regenerating an implementation from the inferred model. The regenerator can produce a translated implementation in a different language and systematically include relevant security and error checks.

from Computer Science and Artificial Intelligence Lab (CSAIL) https://ift.tt/2PJxHVH

Learning Models of Sequential Decision-Making without Complete State Specification using Bayesian Nonparametric Inference and Active Querying

Learning Models of Sequential Decision-Making without Complete State Specification using Bayesian Nonparametric Inference and Active Querying Unhelkar, Vaibhav V.; Shah, Julie A. Learning models of decision-making behavior during sequential tasks is useful across a variety of applications, including human-machine interaction. In this paper, we present an approach to learning such models within Markovian domains based on observing and querying a decision-making agent. In contrast to classical approaches to behavior learning, we do not assume complete knowledge of the state features that impact an agent's decisions. Using tools from Bayesian nonparametric inference and time series of agents decisions, we first provide an inference algorithm to identify the presence of any unmodeled state features that impact decision making, as well as likely candidate models. In order to identify the best model among these candidates, we next provide an active querying approach that resolves model ambiguity by querying the decision maker. Results from our evaluations demonstrate that, using the proposed algorithms, an observer can identify the presence of latent state features, recover their dynamics, and estimate their impact on decisions during sequential tasks.

from Computer Science and Artificial Intelligence Lab (CSAIL) https://ift.tt/2rSu7OJ

A Natural Language Interface for Mobile Devices

A Natural Language Interface for Mobile Devices Katz, Boris; Borchardt, Gary; Felshin, Sue; Mora, Federico Creating a robust, automated capability to respond to natural language requests has been a longstanding goal in the development of intelligent systems. This article describes the StartMobile system, originally developed in 2005-2007, which has served as an important precursor to Apple's Siri system and other commercial natural language interfaces to mobile devices and computational resources. The article begins with a discussion of goals in creating natural language interfaces, continues with a description of the general-purpose START information access system, describes the StartMobile system and its capabilities, and concludes with a discussion of current commercial systems and future directions.

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2ti3vdg

Privacy and Security Risks for National Health Records Systems

Privacy and Security Risks for National Health Records Systems Alawaji, Ahmed; Sollins, Karen A review of national health records (NEHR) systems shows that privacy and security risks have a profound impact on the success of such projects. Countries have different approaches when dealing with privacy and security considerations. The aims of this study were to explore how governments can design secure national health records systems. To do that systematically, we developed a framework to analyze NEHR systems. We then applied the framework to investigate the privacy and security risks in these systems. The studied systems demonstrate that getting privacy and security right have a considerable impact on the success of NEHR projects. Also, our study reveals that the healthcare system structure has a substantial impact on the adoption and usage rates of the system. The studied cases uncover many opportunities for improving privacy and security measures in future projects. The framework demonstrates the utility of applying it to the three cases. SM thesis

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2Ghcvl1

Generating Component-based Supervised Learning Programs From Crowdsourced Examples

Generating Component-based Supervised Learning Programs From Crowdsourced Examples Cambronero, Jose; Rinard, Martin We present CrowdLearn, a new system that processes an existing corpus of crowdsourced machine learning programs to learn how to generate effective pipelines for solving supervised machine learning problems. CrowdLearn uses a probabilistic model of program likelihood, conditioned on the current sequence of pipeline components and on the characteristics of the input data to the next component in the pipeline, to predict candidate pipelines. Our results highlight the effectiveness of this technique in leveraging existing crowdsourced programs to generate pipelines that work well on a range of supervised learning problems.

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2D6PgYG

Typesafety for Explicitly-Coded Probabilistic Inference Procedures

Typesafety for Explicitly-Coded Probabilistic Inference Procedures Atkinson, Eric; Carbin, Michael Researchers have recently proposed several systems that ease the process of developing Bayesian probabilistic inference algorithms. These include systems for automatic inference algorithm synthesis as well as stronger abstractions for manual algorithm development. However, existing systems whose performance relies on the developer manually constructing a part of the inference algorithm have limited support for reasoning about the correctness of the resulting algorithm. In this paper, we present Shuffle, a programming language for developing manual inference algorithms that enforces 1) the basic rules of probability theory and 2) statistical dependencies of the algorithm's corresponding probabilistic model. We have used Shuffle to develop inference algorithms for several standard probabilistic models. Our results demonstrate that Shuffle enables a developer to deliver performant implementations of these algorithms with the added benefit of Shuffle's correctness guarantees.

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2zU8x1Y

The Interval Programming Model Solution Algorithm Experimentation Tools and Results

The Interval Programming Model Solution Algorithm Experimentation Tools and Results Benjamin, Michael R. Interval programming (IvP) is model for representing multi-objective optimization problems along with a set of solution algorithms. This paper describes a set of IvP solution experiments run over randomly generated problem instances, using five different versions of the Recursive Interval Programming ALgorithm (RIPAL). The final version is the algorithm used most extensively in practice, with the first four provided mostly for comparison as the final version is built up in complexity. The full details of the algorithms are outside the scope of this paper, with the focus here being the experimental results, and the software tools and technique used in generating the problem instances. Additional tools are described for facilitating the experiments, including visualization tools, and tools for generating the plots and tables shown in this document. All software tools are available under an open source license, and all problem instances reported here are also available online. This document is meant to supplement other discussions on the IvP model, algorithm, and IvP applications to provide the detail of reporting that would not be possible due to length restrictions of other papers.

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2gqz4I1

Inference and Regeneration of Programs that Manipulate Relational Databases

Inference and Regeneration of Programs that Manipulate Relational Databases Shen, Jiasi; Rinard, Martin We present a new technique that infers models of programs that manipulate relational databases. This technique generates test databases and input commands, runs the program, then observes the resulting outputs and updated databases to infer the model. Because the technique works only with the externally observable inputs, outputs, and databases, it can infer the behavior of programs written in arbitrary languages using arbitrary coding styles and patterns. We also present a technique for automatically regenerating an implementation of the program based on the inferred model. The regenerator can produce a translated implementation in a different language and systematically include relevant security and error checks. We present results that illustrate the use of the technique to eliminate SQL injection vulnerabilities and the translation of applications from Java and Ruby on Rails to Python.

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2vKJ9VN

Multi-Unit Auction Revenue with Possibilistic Beliefs

Multi-Unit Auction Revenue with Possibilistic Beliefs Micali, Silvio; Vlachos, Georgios The revenue of traditional auction mechanisms is benchmarked solely against the players' own valuations, despite the fact that they may also have valuable beliefs about each other's valuations. Not much is known about generating revenue in auctions of multiple identical copies of a same good. (In particular the celebrated Vickrey mechanism has no revenue guarantees.) For such auctions, we (1) put forward an attractive revenue benchmark, based on the players' possibilistic about each other, and (2) construct a mechanism that achieves such benchmark, assuming that the players are two-level rational (where the rationality is in the sense of Aumann).

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2r85Xwn

Autonomous COLREGS Modes and Velocity Functions

Autonomous COLREGS Modes and Velocity Functions Benjamin, Michael R. This paper concerns an implementation of an autonomy system for unmanned surface vessels operating in accordance with the Coast Guard Collision Regulations (COLREGS). The autonomy system is implemented by associating a dedicated ownship behavior module for each contact for collision avoidance. For each behavior, a mode determination is made based on the COLREGS rules, ownship position and trajectory, and the contact position and trajectory. Based on the mode, an appropriate objective function is generated, over the set of possible ownship maneuvers, to bias the vehicle in accordance with the COLREGS. The focus on this paper is solely on (a) the mode determination algorithms, (b) the requisite ownship and contact terms regarding position, trajectory and relative position utilized in the mode determination algorithms, and (c) the form and equations used in making the objective functions associated with each mode.

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2pXnasO

Inference and Regeneration of Programs that Store and Retrieve Data

Inference and Regeneration of Programs that Store and Retrieve Data Rinard, Martin; Shen, Jiasi As modern computation platforms become increasingly complex, their programming interfaces are increasingly difficult to use. This complexity is especially inappropriate given the relatively simple core functionality that many of the computations implement. We present a new approach for obtaining so ware that executes on modern computing platforms with complex programming interfaces. Our approach starts with a simple seed program, written in the language of the developer's choice, that implements the desired core functionality. It then systematically generates inputs and observes the resulting outputs to learn the core functionality. It finally automatically regenerates new code that implements the learned core functionality on the target computing platform. This regenerated code contains both (a) boilerplate code for the complex programming interfaces that the target computing platform presents and (b) systematic error and vulnerability checking code that makes the new implementations robust and secure. By providing a productive new mechanism for capturing and encapsulating knowledge about how to use modern complex interfaces, this new approach promises to greatly reduce the developer effort required to obtain secure, robust so ware that executes on modern computing platforms.

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2oMfWqR

On the Non-Existence of Blockwise 2-Local PRGs with Applications to Indistinguishability Obfuscation

On the Non-Existence of Blockwise 2-Local PRGs with Applications to Indistinguishability Obfuscation Lombardi, Alex; Vaikuntanathan, Vinod Lin and Tessaro (Eprint 2017/250) recently proposed indistinguishability obfuscation and functional encryption candidates and proved their security based on a standard assumption on bilinear maps and a non-standard assumption on ``Goldreich-like'' pseudorandom generators (PRG). In a nutshell, they require the existence of pseudo-random generators $G:\Sigma^n \to \{0,1\}^m$ for some $\mathsf{poly}(n)$-size alphabet $\Sigma$ where each output bit depends on at most two input alphabet symbols, and which achieve sufficiently large stretch. We show a polynomial-time attack against such generators. Our attack uses tools from the literature on two-source extractors (Chor and Goldreich, SICOMP 1988) and efficient refutation of 2-CSPs over large alphabets (Allen, O'Donnell and Witmer, FOCS 2015). Finally, we propose new ways to instantiate the Lin-Tessaro construction that do not immediately fall to our attacks. While we cannot say with any confidence that these modifications are secure, they certainly deserve further cryptanalysis.

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2nrtk7k

The Tensor Algebra Compiler

The Tensor Algebra Compiler Kjolstad, Fredrik; Kamil, Shoaib; Chou, Stephen; Lugato, David; Amarasinghe, Saman Tensor and linear algebra is pervasive in data analytics and the physical sciences. Often the tensors, matrices or even vectors are sparse. Computing expressions involving a mix of sparse and dense tensors, matrices and vectors requires writing kernels for every operation and combination of formats of interest. The number of possibilities is infinite, which makes it impossible to write library code for all. This problem cries out for a compiler approach. This paper presents a new technique that compiles compound tensor algebra expressions combined with descriptions of tensor formats into efficient loops. The technique is evaluated in a prototype compiler called taco, demonstrating competitive performance to best-in-class hand-written codes for tensor and matrix operations.

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2moUfLY

SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group

SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group Rosen, David M.; Carlone, Luca; Bandeira, Afonso S.; Leonard, John J. Many important geometric estimation problems naturally take the form of synchronization over the special Euclidean group: estimate the values of a set of unknown poses given noisy measurements of a subset of their pairwise relative transforms. Examples of this class include the foundational problems of pose-graph simultaneous localization and mapping (SLAM) (in robotics), camera motion estimation (in computer vision), and sensor network localization (in distributed sensing), among others. This inference problem is typically formulated as a nonconvex maximum-likelihood estimation that is computationally hard to solve in general. Nevertheless, in this paper we present an algorithm that is able to efficiently recover certifiably globally optimal solutions of the special Euclidean synchronization problem in a non-adversarial noise regime. The crux of our approach is the development of a semidefinite relaxation of the maximum-likelihood estimation whose minimizer provides an exact MLE so long as the magnitude of the noise corrupting the available measurements falls below a certain critical threshold; furthermore, whenever exactness obtains, it is possible to verify this fact a posteriori, thereby certifying the optimality of the recovered estimate. We develop a specialized optimization scheme for solving large-scale instances of this semidefinite relaxation by exploiting its low-rank, geometric, and graph-theoretic structure to reduce it to an equivalent optimization problem defined on a low-dimensional Riemannian manifold, and then design a Riemannian truncated-Newton trust-region method to solve this reduction efficiently. Finally, we combine this fast optimization approach with a simple rounding procedure to produce our algorithm, SE-Sync. Experimental evaluation on a variety of simulated and real-world pose-graph SLAM datasets shows that SE-Sync is capable of recovering certifiably globally optimal solutions when the available measurements are corrupted by noise up to an order of magnitude greater than that typically encountered in robotics and computer vision applications, and does so more than an order of magnitude faster than the Gauss-Newton-based approach that forms the basis of current state-of-the-art techniques.

from Computer Science and Artificial Intelligence Lab (CSAIL) http://ift.tt/2loFFUW