waashk/dblp huggingface dataset:
fasttrack: efficient and precise dynamic race detection. \begin{abstract} multithreaded programs are notoriously prone to race conditions. prior work on dynamic race detectors includes fast but imprecise race detectors that report false alarms, as well as slow but precise race detectors that never report false alarms. the latter typically use expensive vector clock operations that require time linear in the number of program threads. this paper exploits the insight that the full generality of vector clocks is unnecessary in most cases. that is, we can replace heavyweight vector clocks with an adaptive lightweight representation that, for almost all operations of the target program, requires only constant space and supports constant-time operations. this representation change significantly improves time and space performance, with no loss in precision. experimental results on java benchmarks including the eclipse development environment show that our fasttrack race detector is an order of magnitude faster than a traditional vector-clock race detector, and roughly twice as fast as the high-performance djit+ algorithm. fasttrack is even comparable in speed to eraser on our java benchmarks, while never reporting false alarms.
control-flow refinement and progress invariants for bound analysis. symbolic complexity bounds help programmers understand the performance characteristics of their implementations. existing work provides techniques for statically determining bounds of procedures with simple control-flow. however, procedures with nested loops or multiple paths through a single loop are challenging. in this paper we describe two techniques, control-flow refinement and progress invariants, that together enable estimation of precise bounds for procedures with nested and multi-path loops. control-flow refinement transforms a multi-path loop into a semantically equivalent code fragment with simpler loops by making the structure of path interleaving explicit. we show that this enables non-disjunctive invariant generation tools to find a bound on many procedures for which previous techniques were unable to prove termination. progress invariants characterize relationships between consecutive states that can arise at a program location. we further present an algorithm that uses progress invariants to compute precise bounds for nested loops. the utility of these two techniques goes beyond our application to symbolic bound analysis. in particular, we discuss applications of control-flow refinement to proving safety properties that otherwise require disjunctive invariants. we have applied our methodology to over 670,000 lines of code of a significant microsoft product and were able to find symbolic bounds for 90% of the loops. we are not aware of any other published results that report experiences running a bound analysis on a real code-base.
trace-based just-in-time type specialization for dynamic languages. dynamic languages such as javascript are more difficult to compile than statically typed ones. since no concrete type information is available, traditional compilers need to emit generic code that can handle all possible type combinations at runtime. we present an alternative compilation technique for dynamically-typed languages that identifies frequently executed loop traces at run-time and then generates machine code on the fly that is specialized for the actual dynamic types occurring on each path through the loop. our method provides cheap inter-procedural type specialization, and an elegant and efficient way of incrementally compiling lazily discovered alternative paths through nested loops. we have implemented a dynamic compiler for javascript based on our technique and we have measured speedups of 10x and more for certain benchmark programs.
gc assertions: using the garbage collector to check heap properties. this paper introduces gc assertions, a system interface that programmers can use to check for errors, such as data structure invariant violations, and to diagnose performance problems, such as memory leaks. gc assertions are checked by the garbage collector, which is in a unique position to gather information and answer questions about the lifetime and connectivity of objects in the heap. by piggybacking on existing garbage collector computations, our system is able to check heap properties with very low overhead -- around 3% of total execution time -- low enough for use in a deployed setting. we introduce several kinds of gc assertions and describe how they are implemented in the collector. we also describe our reporting mechanism, which provides a complete path through the heap to the offending objects. we report results on both the performance of our system and the experience of using our assertions to find and repair errors in real-world programs.
laminar: practical fine-grained decentralized information flow control. decentralized information flow control (difc) is a promising model for writing programs with powerful, end-to-end security guarantees. current difc systems that run on commodity hardware can be broadly categorized into two types: language-level and operating system-level difc. language level solutions provide no guarantees against security violations on system resources, like files and sockets. operating system solutions can mediate accesses to system resources, but are inefficient at monitoring the flow of information through fine-grained program data structures. this paper describes laminar, the first system to implement decentralized information flow control using a single set of abstractions for os resources and heap-allocated objects. programmers express security policies by labeling data with secrecy and integrity labels, and then access the labeled data in lexically scoped security regions. laminar enforces the security policies specified by the labels at runtime. laminar is implemented using a modified java virtual machine and a new linux security module. this paper shows that security regions ease incremental deployment and limit dynamic security checks, allowing us to retrofit difc policies on four application case studies. replacing the applications' ad-hoc security policies changes less than 10% of the code, and incurs performance overheads from 1% to 56%. whereas prior difc systems only support limited types of multithreaded programs, laminar supports a more general class of multithreaded difc programs that can access heterogeneously labeled data.
verified validation of lazy code motion. translation validation establishes a posteriori the correctness of a run of a compilation pass or other program transformation. in this paper, we develop an efficient translation validation algorithm for the lazy code motion (lcm) optimization. lcm is an interesting challenge for validation because it is a global optimization that moves code across loops. consequently, care must be taken not to move computations that may fail before loops that may not terminate. our validator includes a specific check for anticipability to rule out such incorrect moves. we present a mechanically-checked proof of correctness of the validation algorithm, using the coq proof assistant. combining our validator with an unverified implementation of lcm, we obtain a lcm pass that is provably semantics-preserving and was integrated in the compcert formally verified compiler.
staged information flow for javascript. modern websites are powered by javascript, a flexible dynamic scripting language that executes in client browsers. a common paradigm in such websites is to include third-party javascript code in the form of libraries or advertisements. if this code were malicious, it could read sensitive information from the page or write to the location bar, thus redirecting the user to a malicious page, from which the entire machine could be compromised. we present an information-flow based approach for inferring the effects that a piece of javascript has on the website in order to ensure that key security properties are not violated. to handle dynamically loaded and generated javascript, we propose a framework for staging information flow properties. our framework propagates information flow through the currently known code in order to compute a minimal set of syntactic residual checks that are performed on the remaining code when it is dynamically loaded. we have implemented a prototype framework for staging information flow. we describe our techniques for handling some difficult features of javascript and evaluate our system's performance on a variety of large real-world websites. our experiments show that static information flow is feasible and efficient for javascript, and that our technique allows the enforcement of information-flow policies with almost no run-time overhead.
lightweight annotations for controlling sharing in concurrent data structures. sharc is a recently developed system for checking data-sharing in multithreaded programs. programmers specify sharing rules (read-only, protected by a lock, etc.) for individual objects, and the sharc compiler enforces these rules using static and dynamic checks. violations of these rules indicate unintended data sharing, which is the underlying cause of harmful data-races. additionally, sharc allows programmers to change the sharing rules for a specific object using a sharing cast, to capture the fact that sharing rules for an object often change during the object's lifetime. sharc was successfully applied to a number of multi-threaded c programs. however, many programs are not readily checkable using sharc because their sharing rules, and changes to sharing rules, effectively apply to whole data structures rather than to individual objects. we have developed a system called shoal to address this shortcoming. in addition to the sharing rules and sharing cast of sharc, our system includes a new concept that we call groups. a group is a collection of objects all having the same sharing mode. each group has a distinguished member called the group leader. when the sharing mode of the group leader changes by way of a sharing cast, the sharing mode of all members of the group also changes. this operation is made sound by maintaining the invariant that at the point of a sharing cast, the only external pointer into the group is the pointer to the group leader. the addition of groups allows checking safe concurrency at the level of data structures rather than at the level of individual objects. we demonstrate the necessity and practicality of groups by applying shoal to a wide range of concurrent c programs (the largest approaching a million lines of code). in all benchmarks groups entail low annotation burden and no significant additional performance overhead.
literace: effective sampling for lightweight data-race detection. data races are one of the most common and subtle causes of pernicious concurrency bugs. static techniques for preventing data races are overly conservative and do not scale well to large programs. past research has produced several dynamic data race detectors that can be applied to large programs. they are precise in the sense that they only report actual data races. however, dynamic data race detectors incur a high performance overhead, slowing down a program's execution by an order of magnitude. in this paper we present literace, a very lightweight data race detector that samples and analyzes only selected portions of a program's execution. we show that it is possible to sample a multithreaded program at a low frequency, and yet, find infrequently occurring data races. we implemented literace using microsoft's phoenix compiler. our experiments with several microsoft programs, apache, and firefox show that literace is able to find more than 70% of data races by sampling less than 2% of memory accesses in a given program execution.
a study of memory management for web-based applications on multicore processors. more and more server workloads are becoming web-based. in these web-based workloads, most of the memory objects are used only during one transaction. we study the effect of the memory management approaches on the performance of such web-based applications on two modern multicore processors. in particular, using six php applications, we compare a general-purpose allocator (the default allocator of the php runtime) and a region-based allocator, which can reduce the cost of memory management by not supporting per-object free. the region-based allocator achieves better performance for all workloads on one processor core due to its smaller memory management cost. however, when using eight cores, the region-based allocator suffers from hidden costs of increased bus traffics and the performance is reduced for many workloads by as much as 27.2% compared to the default allocator. this is because the memory bandwidth tends to become a bottleneck in systems with multicore processors. we propose a new memory management approach, defrag-dodging, to maximize the performance of the web-based workloads on multicore processors. in our approach, we reduce the memory management cost by avoiding defragmentation overhead in the malloc and free functions during a transaction. we found that the transactions in web-based applications are short enough to ignore heap fragmentation, and hence the costs of the defrag-mentation activities in existing general-purpose allocators outweigh their benefits. by comparing our approach against the region-based approach, we show that a per-object free capability can reduce bus traffic and achieve higher performance on multicore processors. we demonstrate that our defrag-dodging approach improves the performance of all the evaluated applications on both processors by up to 11.4% and 51.5% over the default allocator and the region-based allocator, respectively.
stretching transactional memory. transactional memory (tm) is an appealing abstraction for programming multi-core systems. potential target applications for tm, such as business software and video games, are likely to involve complex data structures and large transactions, requiring specific software solutions (stm). so far, however, stms have been mainly evaluated and optimized for smaller scale benchmarks. we revisit the main stm design choices from the perspective of complex workloads and propose a new stm, which we call swisstm. in short, swisstm is lock- and word-based and uses (1) optimistic (commit-time) conflict detection for read/write conflicts and pessimistic (encounter-time) conflict detection for write/write conflicts, as well as (2) a new two-phase contention manager that ensures the progress of long transactions while inducing no overhead on short ones. swisstm outperforms state-of-the-art stm implementations, namely rstm, tl2, and tinystm, in our experiments on stmbench7, stamp, lee-tm and red-black tree benchmarks. beyond swisstm, we present the most complete evaluation to date of the individual impact of various stm design choices on the ability to support the mixed workloads of large applications.
a randomized dynamic program analysis technique for detecting real deadlocks. we present a novel dynamic analysis technique that finds real deadlocks in multi-threaded programs. our technique runs in two stages. in the first stage, we use an imprecise dynamic analysis technique to find potential deadlocks in a multi-threaded program by observing an execution of the program. in the second stage, we control a random thread scheduler to create the potential deadlocks with high probability. unlike other dynamic analysis techniques, our approach has the advantage that it does not give any false warnings. we have implemented the technique in a prototype tool for java, and have experimented on a number of large multi-threaded java programs. we report a number of previously known and unknown real deadlocks that were found in these benchmarks.
merlin: specification inference for explicit information flow problems. the last several years have seen a proliferation of static and runtime analysis tools for finding security violations that are caused by explicit information flow in programs. much of this interest has been caused by the increase in the number of vulnerabilities such as cross-site scripting and sql injection. in fact, these explicit information flow vulnerabilities commonly found in web applications now outnumber vulnerabilities such as buffer overruns common in type-unsafe languages such as c and c++. tools checking for these vulnerabilities require a specification to operate. in most cases the task of providing such a specification is delegated to the user. moreover, the efficacy of these tools is only as good as the specification. unfortunately, writing a comprehensive specification presents a major challenge: parts of the specification are easy to miss, leading to missed vulnerabilities; similarly, incorrect specifications may lead to false positives. this paper proposes merlin, a new approach for automatically inferring explicit information flow specifications from program code. such specifications greatly reduce manual labor, and enhance the quality of results, while using tools that check for security violations caused by explicit information flow. beginning with a data propagation graph, which represents interprocedural flow of information in the program, merlin aims to automatically infer an information flow specification. merlin models information flow paths in the propagation graph using probabilistic constraints. a naive modeling requires an exponential number of constraints, one per path in the propagation graph. for scalability, we approximate these path constraints using constraints on chosen triples of nodes, resulting in a cubic number of constraints. we characterize this approximation as a probabilistic abstraction, using the theory of probabilistic refinement developed by mciver and morgan. we solve the resulting system of probabilistic constraints using factor graphs, which are a well-known structure for performing probabilistic inference. we experimentally validate the merlin approach by applying it to 10 large business-critical web applications that have been analyzed with cat.net, a state-of-the-art static analysis tool for .net. we find a total of 167 new confirmed specifications, which result in a total of 322 additional vulnerabilities across the 10 benchmarks. more accurate specifications also reduce the false positive rate: in our experiments, merlin-inferred specifications result in 13 false positives being removed; this constitutes a 15% reduction in the cat.net false positive rate on these 10 programs. the final false positive rate for cat.net after applying merlin in our experiments drops to under 1%.
petabricks: a language and compiler for algorithmic choice. it is often impossible to obtain a one-size-fits-all solution for high performance algorithms when considering different choices for data distributions, parallelism, transformations, and blocking. the best solution to these choices is often tightly coupled to different architectures, problem sizes, data, and available system resources. in some cases, completely different algorithms may provide the best performance. current compiler and programming language techniques are able to change some of these parameters, but today there is no simple way for the programmer to express or the compiler to choose different algorithms to handle different parts of the data. existing solutions normally can handle only coarse-grained, library level selections or hand coded cutoffs between base cases and recursive cases. we present petabricks, a new implicitly parallel language and compiler where having multiple implementations of multiple algorithms to solve a problem is the natural way of programming. we make algorithmic choice a first class construct of the language. choices are provided in a way that also allows our compiler to tune at a finer granularity. the petabricks compiler autotunes programs by making both fine-grained as well as algorithmic choices. choices also include different automatic parallelization techniques, data distributions, algorithmic parameters, transformations, and blocking. additionally, we introduce novel techniques to autotune algorithms for different convergence criteria. when choosing between various direct and iterative methods, the petabricks compiler is able to tune a program in such a way that delivers near-optimal efficiency for any desired level of accuracy. the compiler has the flexibility of utilizing different convergence criteria for the various components within a single algorithm, providing the user with accuracy choice alongside algorithmic choice.
a fast and efficient algorithm for low-rank approximation of a matrix. the low-rank matrix approximation problem involves finding of a rank k version of a m x n matrix a, labeled ak, such that ak is as "close" as possible to the best svd approximation version of a at the same rank level. previous approaches approximate matrix a by non-uniformly adaptive sampling some columns (or rows) of a, hoping that this subset of columns contain enough information about a. the sub-matrix is then used for the approximation process. however, these approaches are often computationally intensive due to the complexity in the adaptive sampling. in this paper, we propose a fast and efficient algorithm which at first pre-processes matrix a in order to spread out information (energy) of every columns (or rows) of a, then randomly selects some of its columns (or rows). finally, a rank-k approximation is generated from the row space of these selected sets. the preprocessing step is performed by uniformly randomizing signs of entries of a and transforming all columns of a by an orthonormal matrix f with existing fast implementation (e.g. hadamard, fft, dct...). our main contribution is summarized as follows. 1) we show that by uniformly selecting at random d rows of the preprocessed matrix with d = ( 1/η k max {log k, log 1/β} ), we guarantee the relative frobenius norm error approximation: (1 + η) norm{a - ak}f with probability at least 1 - 5β. 2) with d above, we establish a spectral norm error approximation: (2 + √2m/d) norm{a - ak}2 with probability at least 1 - 2β. 3) the algorithm requires 2 passes over the data and runs in time (mn log d + (m+n) d2) which, as far as the best of our knowledge, is the fastest algorithm when the matrix a is dense. 4) as a bonus, applying this framework to the well-known least square approximation problem min norm{a x - b} where a ∈ rm x r, we show that by randomly choosing d = (1/η γ r log m), the approximation solution is proportional to the optimal one with a factor of η and with extremely high probability, (1 - 6 m-γ), say.
on cryptography with auxiliary input. we study the question of designing cryptographic schemes which are secure even if an arbitrary function f(sk) of the secret key is leaked, as long as the secret key sk is still (exponentially) hard to compute from this auxiliary input. this setting of auxiliary input is more general than the more traditional setting, which assumes that some of information about the secret key sk may be leaked, but sk still has high min-entropy left. in particular, we deal with situations where f(sk) information-theoretically determines the entire secret key sk. as our main result, we construct cpa/cca secure symmetric encryption schemes that remain secure with exponentially hard-to-invert auxiliary input. we give several applications of such schemes. * we construct an average-case obfuscator for the class of point functions, which remains secure with exponentially hard-to-invert auxiliary input, and is reusable. * we construct a reusable and robust extractor that remains secure with exponentially hard-to-invert auxiliary input. our results rely on a new cryptographic assumption, learning subspace-with-noise (lsn), which is related to the well known learning parity-with-noise (lpn) assumption.