waashk/dblp huggingface dataset:
temporal search: detecting hidden malware timebombs with virtual machines. worms, viruses, and other malware can be ticking bombs counting down to a specific time, when they might, for example, delete files or download new instructions from a public web server. we propose a novel virtual-machine-based analysis technique to automatically discover the timetable of a piece of malware, or when events will be triggered, so that other types of analysis can discern what those events are. this information can be invaluable for responding to rapid malware, and automating its discovery can provide more accurate information with less delay than careful human analysis.developing an automated system that produces the timetable of a piece of malware is a challenging research problem. in this paper, we describe our implementation of a key component of such a system: the discovery of timers without making assumptions about the integrity of the infected system's kernel. our technique runs a virtual machine at slightly different rates of perceived time (time as seen by the virtual machine), and identifies time counters by correlating memory write frequency to timer interrupt frequency.we also analyze real malware to assess the feasibility of using full-system, machine-level symbolic execution on these timers to discover predicates. because of the intricacies of the gregorian calendar (leap years, different number of days in each month, etc.) these predicates will not be direct expressions on the timer but instead an annotated trace; so we formalize the calculation of a timetable as a weakest precondition calculation. our analysis of six real worms sheds light on two challenges for future work: 1) time-dependent malware behavior often does not follow a linear timetable; and 2) that an attacker with knowledge of the analysis technique can evade analysis. our current results are promising in that with simple symbolic execution we are able to discover predicates on the day of the month for four real worms. then through more traditional manual analysis we conclude that a more control-flow-sensitive symbolic execution implementation would discover all predicates for the malware we analyzed.
optimistic parallelism benefits from data partitioning. recent studies of irregular applications such as finite-element mesh generators and data-clustering codes have shown that these applications have a generalized data parallelism arising from the use of iterative algorithms that perform computations on elements of worklists. in some irregular applications, the computations on different elements are independent. in other applications, there may be complex patterns of dependences between these computations. the galois system was designed to exploit this kind of irregular data parallelism on multicore processors. its main features are (i) two kinds of set iterators for expressing worklist-based data parallelism, and (ii) a runtime system that performs optimistic parallelization of these iterators, detecting conflicts and rolling back computations as needed. detection of conflicts and rolling back iterations requires information from class implementors. in this paper, we introduce mechanisms to improve the execution efficiency of galois programs: data partitioning, data-centric work assignment, lock coarsening, and over-decomposition. these mechanisms can be used to exploit locality of reference, reduce mis-speculation, and lower synchronization overhead. we also argue that the design of the galois system permits these mechanisms to be used with relatively little modification to the user code. finally, we present experimental results that demonstrate the utility of these mechanisms.
xoc, an extension-oriented compiler for systems programming. today's system programmers go to great lengths to extend the languages in which they program. for instance, system-specific compilers find errors in linux and other systems, and add support for specialized control flow to qt and event-based programs. these compilers are difficult to build and cannot always understand each other's language changes. however, they can greatly improve code understandability and correctness, advantages that should be accessible to all programmers. we describe an extension-oriented compiler for c called xoc. an extension-oriented compiler, unlike a conventional extensible compiler, implements new features via many small extensions that are loaded together as needed. xoc gives extension writers full control over program syntax and semantics while hiding many compiler internals. xoc programmers concisely define powerful compiler extensions that, by construction, can be combined; even some parts of the base compiler, such as gnu c compatibility, are structured as extensions. xoc is based on two key interfaces. syntax patterns allow extension writers to manipulate language fragments using concrete syntax. lazy computation of attributes allows extension writers to use the results of analyses by other extensions or the core without needing to worry about pass scheduling. extensions built using xoc include xsparse, a 345-line extension that mimics sparse, linux's c front end, and xlambda, a 170-line extension that adds function expressions to c. an evaluation of xoc using these and 13 other extensions shows that xoc extensions are typically more concise than equivalent extensions written for conventional extensible compilers and that it is possible to compose extensions.
accelerating two-dimensional page walks for virtualized systems. nested paging is a hardware solution for alleviating the software memory management overhead imposed by system virtualization. nested paging complements existing page walk hardware to form a two-dimensional (2d) page walk, which reduces the need for hypervisor intervention in guest page table management. however, the extra dimension also increases the maximum number of architecturally-required page table references. this paper presents an in-depth examination of the 2d page table walk overhead and options for decreasing it. these options include using the amd opteron processor's page walk cache to exploit the strong reuse of page entry references. for a mix of server and spec benchmarks, the presented results show a 15%-38% improvement in guest performance by extending the existing page walk cache to also store the nested dimension of the 2d page walk. caching nested page table translations and skipping multiple page entry references produce an additional 3%-7% improvement. much of the remaining 2d page walk overhead is due to low-locality nested page entry references, which result in additional memory hierarchy misses. by using large pages, the hypervisor can eliminate many of these long-latency accesses and further improve the guest performance by 3%-22%.
archipelago: trading address space for reliability and security. memory errors are a notorious source of security vulnerabilities that can lead to service interruptions, information leakage and unauthorized access. because such errors are also difficult to debug, the absence of timely patches can leave users vulnerable to attack for long periods of time. a variety of approaches have been introduced to combat these errors, but these often incur large runtime overheads and generally abort on errors, threatening availability. this paper presents archipelago, a runtime system that takes advantage of available address space to substantially reduce the likelihood that a memory error will affect program execution. archipelago randomly allocates heap objects far apart in virtual address space, effectively isolating each object from buffer overflows. archipelago also protects against dangling pointer errors by preserving the contents of freed objects after they are freed. archipelago thus trades virtual address space---a plentiful resource on 64-bit systems---for significantly improved program reliability and security, while limiting physical memory consumption by tracking the working set of an application and compacting cold objects. we show that archipelago allows applications to continue to run correctly in the face of thousands of memory errors. across a suite of server applications, archipelago's performance overhead is 6% on average (between -7% and 22%), making it especially suitable to protect servers that have known security vulnerabilities due to heap memory errors.
understanding and visualizing full systems with data flow tomography. it is not uncommon for modern systems to be composed of a variety of interacting services, running across multiple machines in such a way that most developers do not really understand the whole system. as abstraction is layered atop abstraction, developers gain the ability to compose systems of extraordinary complexity with relative ease. however, many software properties, especially those that cut across abstraction layers, become very difficult to understand in such compositions. the communication patterns involved, the privacy of critical data, and the provenance of information, can be difficult to find and understand, even with access to all of the source code. the goal of data flow tomography is to use the inherent information flow of such systems to help visualize the interactions between complex and interwoven components across multiple layers of abstraction. in the same way that the injection of short-lived radioactive isotopes help doctors trace problems in the cardiovascular system, the use of "data tagging" can help developers slice through the extraneous layers of software and pin-point those portions of the system interacting with the data of interest. to demonstrate the feasibility of this approach we have developed a prototype system in which tags are tracked both through the machine and in between machines over the network, and from which novel visualizations of the whole system can be derived. we describe the system-level challenges in creating a working system tomography tool and we qualitatively evaluate our system by examining several example real world scenarios.
softsig: software-exposed hardware signatures for code analysis and optimization. many code analysis techniques for optimization, debugging, or parallelization need to perform runtime disambiguation of sets of addresses. such operations can be supported efficiently and with low complexity with hardware signatures. to enable flexible use of signatures, this paper proposes to expose a signature register file to the software through a rich isa. the software has great flexibility to decide, for each signature,which addresses to collect and which addresses to disambiguate against. we call this architecture softsig. in addition, as an example of softsig use, we show how to detect redundant function calls efficiently and eliminate them dynamically. we call this algorithm memoise. on average for five popular applications, memoise reduces the number of dynamic instructions by 9.3%, thereby reducing the execution time of the applications by 9%.
learning from mistakes: a comprehensive study on real world concurrency bug characteristics. the reality of multi-core hardware has made concurrent programs pervasive. unfortunately, writing correct concurrent programs is difficult. addressing this challenge requires advances in multiple directions, including concurrency bug detection, concurrent program testing, concurrent programming model design, etc. designing effective techniques in all these directions will significantly benefit from a deep understanding of real world concurrency bug characteristics. this paper provides the first (to the best of our knowledge) comprehensive real world concurrency bug characteristic study. specifically, we have carefully examined concurrency bug patterns, manifestation, and fix strategies of 105 randomly selected real world concurrency bugs from 4 representative server and client open-source applications (mysql, apache, mozilla and openoffice). our study reveals several interesting findings and provides useful guidance for concurrency bug detection, testing, and concurrent programming language design. some of our findings are as follows: (1) around one third of the examined non-deadlock concurrency bugs are caused by violation to programmers' order intentions, which may not be easily expressed via synchronization primitives like locks and transactional memories; (2) around 34% of the examined non-deadlock concurrency bugs involve multiple variables, which are not well addressed by existing bug detection tools; (3) about 92% of the examined concurrency bugs canbe reliably triggered by enforcing certain orders among no more than 4 memory accesses. this indicates that testing concurrent programs can target at exploring possible orders among every small groups of memory accesses, instead of among all memory accesses; (4) about 73% of the examinednon-deadlock concurrency bugs were not fixed by simply adding or changing locks, and many of the fixes were not correct at the first try, indicating the difficulty of reasoning concurrent execution by programmers.
streamware: programming general-purpose multicore processors using streams. recently, the number of cores on general-purpose processors has been increasing rapidly. using conventional programming models, it is challenging to effectively exploit these cores for maximal performance. an interesting alternative candidate for programming multiple cores is the stream programming model, which provides a framework for writing programs in a sequential-style while greatly simplifying the task of automatic parallelization. it has been shown that not only traditional media/image applications but also more general-purpose data-intensive applications can be expressed in the stream programming style. in this paper, we investigate the potential to use the stream programming model to efficiently utilize commodity multicore general-purpose processors (e.g., intel/amd). although several stream languages and stream compilers have recently been developed, they typically target special-purpose stream processors. in contrast, we propose a flexible software system, streamware, which automatically maps stream programs onto a wide variety of general-purpose multicore processor configurations. we leverage existing compilation framework for stream processors and design a runtime environment which takes as input the output of these stream compilers in the form of machine-independent stream virtual machine code. the runtime environment assigns work to processor cores considering processor/cache configurations and adapts to workload variations. we evaluate this approach for a few general-purpose scientific applications on real hardware and a cycle-level simulator set-up to showcase scaling and contention issues. the results show that the stream programming model is a good choice for efficiently exploiting modern and future multicore cpus for an important class of applications.
communication optimizations for global multi-threaded instruction scheduling. the recent shift in the industry towards chip multiprocessor (cmp) designs has brought the need for multi-threaded applications to mainstream computing. as observed in several limit studies, most of the parallelization opportunities require looking for parallelism beyond local regions of code. to exploit these opportunities, especially for sequential applications, researchers have recently proposed global multi-threaded instruction scheduling techniques, including dswp and gremio. these techniques simultaneously schedule instructions from large regions of code, such as arbitrary loop nests or whole procedures, and have been shown to be effective at extracting threads for many applications. a key enabler of these global instruction scheduling techniques is the multi-threaded code generation (mtcg) algorithm proposed in [16], which generates multi-threaded code for any partition of the instructions into threads. this algorithm inserts communication and synchronization instructions in order to satisfy all inter-thread dependences. in this paper, we present a general compiler framework, coco, to optimize the communication and synchronization instructions inserted by the mtcg algorithm. this framework, based on thread-aware data-flow analyses and graph min-cut algorithms, appropriately models andoptimizes all kinds of inter-thread dependences, including register, memory, and control dependences. our experiments, using a fully automatic compiler implementation of these techniques, demonstrate significant reductions (about 30% on average) in the number of dynamic communication instructions in code parallelized with dswp and gremio. this reduction in communication translates to performance gains of up to 40%.
better bug reporting with better privacy. software vendors collect bug reports from customers to improve the quality of their software. these reports should include the inputs that make the software fail, to enable vendors to reproduce the bug. however, vendors rarely include these inputs in reports because they may contain private user data. we describe a solution to this problem that provides software vendors with new input values that satisfy the conditions required to make the software follow the same execution path until it fails, but are otherwise unrelated with the original inputs. these new inputs allow vendors to reproduce the bug while revealing less private information than existing approaches. additionally, we provide a mechanism to measure the amount of information revealed in an error report. this mechanism allows users to perform informed decisions on whether or not to submit reports. we implemented a prototype of our solution and evaluated it with real errors in real programs. the results show that we can produce error reports that allow software vendors to reproduce bugs while revealing almost no private information.
improving the performance of object-oriented languages with dynamic predication of indirect jumps. indirect jump instructions are used to implement increasingly-common programming constructs such as virtual function calls, switch-case statements, jump tables, and interface calls. the performance impact of indirect jumps is likely to increase because indirect jumps with multiple targets are difficult to predict even with specialized hardware. this paper proposes a new way of handling hard-to-predict indirect jumps: dynamically predicating them. the compiler (static or dynamic) identifies indirect jumps that are suitable for predication along with their control-flow merge (cfm) points. the hardware predicates theinstructions between different targets of the jump and its cfm point if the jump turns out to be hard-to-predict at run time. if the jump would actually have been mispredicted, its dynamic predication eliminates a pipeline flush, thereby improving performance. our evaluations show that dynamic indirect jump predication (dip) improves the performance of a set of object-oriented applications including the java dacapo benchmark suite by 37.8% compared to a commonly-used branch target buffer based predictor, while also reducing energy consumption by 24.8%. we compare dip to three previously proposed indirect jump predictors and find that it provides the best performance and energy-efficiency.
a comparison of software and hardware techniques for x86 virtualization. until recently, the x86 architecture has not permitted classical trap-and-emulate virtualization. virtual machine monitors for x86, such as vmware ® workstation and virtual pc, have instead used binary translation of the guest kernel code. however, both intel and amd have now introduced architectural extensions to support classical virtualization.we compare an existing software vmm with a new vmm designed for the emerging hardware support. surprisingly, the hardware vmm often suffers lower performance than the pure software vmm. to determine why, we study architecture-level events such as page table updates, context switches and i/o, and find their costs vastly different among native, software vmm and hardware vmm execution.we find that the hardware support fails to provide an unambiguous performance advantage for two primary reasons: first, it offers no support for mmu virtualization; second, it fails to co-exist with existing software techniques for mmu virtualization. we look ahead to emerging techniques for addressing this mmu virtualization problem in the context of hardware-assisted virtualization.
automatic generation of peephole superoptimizers. peephole optimizers are typically constructed using human-written pattern matching rules, an approach that requires expertise and time, as well as being less than systematic at exploiting all opportunities for optimization. we explore fully automatic construction of peephole optimizers using brute force superoptimization. while the optimizations discovered by our automatic system may be less general than human-written counterparts, our approach has the potential to automatically learn a database of thousands to millions of optimizations, in contrast to the hundreds found in current peephole optimizers. we show experimentally that our optimizer is able to exploit performance opportunities not found by existing compilers; in particular, we show speedups from 1.7 to a factor of 10 on some compute intensive kernels over a conventional optimizing compiler.
integrated network interfaces for high-bandwidth tcp/ip. this paper proposes new network interface controller (nic) designs that take advantage of integration with the host cpu to provide increased flexibility for operating system kernel-based performance optimization.we believe that this approach is more likely to meet the needs of current and future high-bandwidth tcp/ip networking on end hosts than the current trend of putting more complexity in the nic, while avoiding the need to modify applications and protocols. this paper presents two such nics. the first, the simple integrated nic (sinic), is a minimally complex design that moves the responsibility for managing the network fifos from the nic to the kernel. despite this closer interaction between the kernel and the nic, sinic provides performance equivalent to a conventional dma-based nic without increasing cpu overhead. the second design, v-sinic, adds virtual per-packet registers to sinic, enabling parallel packet processing while maintaining a fifo model. v-sinic allows the kernel to decouple examining a packet's header from copying its payload to memory. we exploit this capability to implement a true zero-copy receive optimization in the linux 2.6 kernel, providing bandwidth improvements of over 50% on unmodified sockets-based receive-intensive benchmarks.
bell: bit-encoding online memory leak detection. memory leaks compromise availability and security by crippling performance and crashing programs. leaks are difficult to diagnose because they have no immediate symptoms. online leak detection tools benefit from storing and reporting per-object sites (e.g., allocation sites) for potentially leaking objects. in programs with many small objects, per-object sites add high space overhead, limiting their use in production environments.this paper introduces bit-encoding leak location (bell), a statistical approach that encodes per-object sites to a single bit per object. a bit loses information about a site, but given sufficient objects that use the site and a known, finite set of possible sites, bell uses brute-force decoding to recover the site with high accuracy.we use this approach to encode object allocation and last-use sites in sleigh, a new leak detection tool. sleigh detects stale objects (objects unused for a long time) and uses bell decoding to report their allocation and last-use sites. our implementation steals four unused bits in the object header and thus incurs no per-object space overhead. sleigh's instrumentation adds 29% execution time overhead, which adaptive profiling reduces to 11%. sleigh's output is directly useful for finding and fixing leaks in spec jbb2000 and eclipse, although sufficiently many objects must leak before bell decoding can report sites with confidence. bell is suitable for other leak detection approaches that store per-object sites, and for other problems amenable to statistical per-object metadata.