Several studies showed that misuses of cryptographic APIs are common in real-world code (e.g., Apache projects and Android apps). There exist several open-sourced and commercial security tools that automatically screen Java programs to detect misuses. To compare their accuracy and security guarantees, we develop two comprehensive benchmarks named CryptoAPI-Bench and ApacheCryptoAPI-Bench. CryptoAPI-Bench consists of 181 unit test cases that cover basic cases, as well as complex cases, including interprocedural, field sensitive, multiple class test cases, and path sensitive data flow of misuse cases. The benchmark also includes correct cases for testing false-positive rates. The ApacheCryptoAPI-Bench consists of 121 cryptographic cases from 10 Apache projects. We evaluate four tools, namely, SpotBugs, CryptoGuard, CrySL, and another tool (anonymous) using both benchmarks. We present their performance and comparative analysis. The ApacheCryptoAPI-Bench also examines the scalability of the tools. Our benchmarks are useful for advancing state-of-the-art solutions in the space of misuse detection.

As fuzz testing has passed its 30th anniversary, and in the face of the incredible progress in fuzz testing techniques and tools, the question arises if the classic, basic fuzz technique is still useful and applicable? In that tradition, we have updated the basic fuzz tools and testing scripts and applied them to a large collection of Unix utilities on Linux, FreeBSD, and MacOS. As before, our failure criteria was whether the program crashed or hung. We found that 9 crash or hang out of 74 utilities on Linux, 15 out of 78 utilities on FreeBSD, and 12 out of 76 utilities on MacOS. A total of 24 different utilities failed across the three platforms. We note that these failure rates are somewhat higher than our in previous 1995, 2000, and 2006 studies of the reliability of command line utilities. In the basic fuzz tradition, we debugged each failed utility and categorized the causes the failures. Classic categories of failures, such as pointer and array errors and not checking return codes, were still broadly present in the current results. In addition, we found a couple of new categories of failures appearing. We present examples of these failures to illustrate the programming practices that allowed them to happen. As a side note, we tested the limited number of utilities available in a modern programming language (Rust) and found them to be of no better reliability than the standard ones.

Binary code analysis is widely used to help assess a program's correctness, performance, and provenance. Binary analysis applications often construct control flow graphs, analyze data flow, and use debugging information to understand how machine code relates to source lines, inlined functions, and data types. To date, binary analysis has been single-threaded, which is too slow for convenient use in performance tuning workflows where it is used to help attribute performance to complex applications with large binaries.

Cryptographic API misuses seriously threatens software security. Automatic screening of cryptographic misuse vulnerabilities has been a popular and important line of research over the years. However, the vision of producing a scalable detection tool that developers can routinely use to screen millions of line of code has not been achieved yet. Our main technical goal is to attain a high precision and high throughput approach based on specialized program analysis. Specifically, we design inter-procedural program slicing on top of a new on-demand flow-, context- and field- sensitive data flow analysis. Our current prototype named CryptoGuard can detect a wide range of Java cryptographic API misuses with a precision of 98.61%, when evaluated on 46 complex Apache Software Foundation projects (including, Spark, Ranger, and Ofbiz). Our evaluation on 6,181 Android apps also generated many security insights. We created a comprehensive benchmark named CryptoApi-Bench with 40-unit basic cases and 131-unit advanced cases for in-depth comparison with leading solutions (e.g., SpotBugs, CrySL, Coverity). To make CryptoGuard widely accessible, we are in the process of integrating CryptoGuard with the Software Assurance Marketplace (SWAMP). SWAMP is a popular no-cost service for continuous software assurance and static code analysis.

GPU accelerators have become common on today's leadership-class computing platforms. Effective exploitation of the additional parallelism offered by GPUs is fraught with challenges. A key performance challenge faced by developers is how to limit the time consumed by synchronizations between the CPU and GPU. We introduce the extended feed-forward measurement (FFM) performance tool that provides an automated detection of synchronization problems, identifies if the synchronization problem is a component of a larger construct that exhibits a problem beyond an individual synchronization operation, identifies remedies that can correct the issue, and in some cases automatically applies remedies to problems exhibited by larger constructs. The extended FFM performance tool identifies three causes of unnecessary synchronizations: a problem caused by a single operation, a problem caused by memory management issues, and a problem caused by a memory transfer. The extended FFM model prescribes remedies for each construct and can automatically apply remedies for memory management and memory transfer cause problems. We created an implementation of the extended FFM performance tool and employed it to identify and automatically correct problems in three real-world scientific applications, resulting in an automatically obtained reduction in execution time between 9% and 43%.

Cryptographic API misuses seriously threaten software security. Automatic screening of cryptographic misuse vulnerabilities has been a popular and important line of research over the years. However, the vision of producing a scalable detection tool that developers can routinely use to screen millions of line of code has not been achieved yet. Our main technical goal is to attain a high precision and high throughput approach based on specialized program analysis. Specifically, we design inter-procedural program slicing on top of a new on-demand flow-, context- and field- sensitive data flow analysis. Our current prototype named CryptoGuard can detect a wide range of Java cryptographic API misuses with a precision of 98.61%,, when evaluated on 46 complex Apache Software Foundation projects (including, Spark, Ranger, and Ofbiz). Our evaluation on 6,181 Android apps also generated many security insights. We created a comprehensive benchmark named CryptoAPI-Bench with 40-unit basic cases and 131-unit advanced cases for in-depth comparison with leading solutions (e.g., SpotBugs, CrySL, Coverity). To make CryptoGuard widely accessible, we are in the process of integrating CryptoGuard with the Software Assurance Marketplace (SWAMP). SWAMP is a popular no-cost service for continuous software assurance and static code analysis.

GPU accelerators have become common on today's leadership-class computing platforms. Exploiting the additional parallelism offered by GPUs is fraught with challenges. A key performance challenge faced by developers is how to limit the time consumed by synchronization and memory transfers between the CPU and GPU. We introduce the feed-forward measurement (FFM) performance tool model that automates the identification of unnecessary or inefficient synchronization and memory transfer, providing an estimate of potential benefit if the problem were fixed. FFM uses a new multi-stage/multi-run instrumentation model that adjusts instrumentation based application behavior on prior runs, guiding FFM to problematic GPU operations that were previously unknown. The collected data feeds a new analysis model that gives an accurate estimate of potential benefit of fixing the problem. We created an implementation of FFM called Diogenes that we have used to identify problems in four real-world scientific applications.

Leadership class systems with nodes containing many-core accelerators, such as GPUs, have the potential to increase the performance of applications. Effectively exploiting the parallelism provided by many-core accelerators requires developers to identify where accelerator parallelization would provide benefit and ensuring efficient interaction between the CPU and accelerator. In the abstract, these issues appear straightforward and well understood. However, we have found that significant untapped performance opportunities exist in these areas even in well-known, heavily optimized, real world applications created by experienced GPU developers. These untapped performance opportunities exist because accelerated libraries can create unexpected synchronization delay and memory transfer requests, interaction between accelerated libraries can cause unexpected inefficiencies when combined, and vectorization opportunities can be hidden by the structure of the program. In applications we have studied (Qball, QBox, Hoomd-blue, LAMMPs, and cuIBM), exploiting these opportunities resulted in reduction of their execution time by 18%-87%. In this work, we provide concrete evidence of the existence and impact that these performance issues have on real world applications today. We characterize the missed performance opportunities we have identified by their underlying cause and describe a preliminary design of detection methods that can be used by performance tools to identify these missed opportunities.

Decoding binary executable files is a critical facility for software analysis, including debugging, performance monitoring, malware detection, cyber forensics, and sandboxing, among other techniques. As a foundational capability, binary decoding must be consistently correct for the techniques that rely on it to be viable. Unfortunately, modern instruction sets are huge and the encodings are complex, so as a result, modern binary decoders are buggy. In this paper, we present a testing methodology that automatically infers structural information for an instruction set and uses the inferred structure to efficiently generate structured-random test cases independent of the instruction set being tested. Our testing methodology includes automatic output verification using differential analysis and reassembly to generate error reports. This testing methodology requires little instruction-set-specific knowledge, allowing rapid testing of decoders for new architectures and extensions to existing ones. We have implemented our testing procedure in a tool name Fleece and used it to test multiple binary decoders (Intel XED, libopcodes, LLVM, Dyninst and Capstone) on multiple architectures (x86, ARM and PowerPC). Our testing efficiently covered thousands of instruction format variations for each instruction set and uncovered decoding bugs in every decoder we tested.

Software assurance tools – tools that scan the source or binary code of a program to find weaknesses – are the first line of defense in assessing the security of a software project. Even though there are a plethora of such tools available, with multiple tools for almost every programming language, adoption of these tools is spotty at best. And even though different tools have distinct abilities to find different kinds of weaknesses, the use of multiple tools is even less common. And when the tools are used (or attempted to be used), they are often used in ways that reduce their effectiveness. We present a step-by-step discussion of how to use a software assurance tool, describing the challenges that can occur in this process. We also present quantitative evidence about the effects that can occur when assurance tools are applied in a simplistic or naive way. We base this presentation on our direct experiences with using a wide variety of assurance tools. We then present the US Department of Homeland Security funded Software Assurance Marketplace (SWAMP), an open facility where users can upload their software to have it automatically and continually assessed by a variety of tools. The goal of the SWAMP is to simplify the task of the programmer in using assurance tools, thereby removing many of the obstacles to their adoption. Copyright © 2016 The Authors. Software: Practice and Experience Published by John Wiley & Sons, Ltd.

Binary code analysis is an enabling technique for many applications. Modern compilers and run-time libraries have introduced significant complexities to binary code, which negatively affect the capabilities of binary analysis tool kits to analyze binary code, and may cause tools to report inaccurate information about binary code. Analysts may hence be confused and applications based on these tool kits may have degrading quality. We examine the problem of constructing control flow graphs from binary code and labeling the graphs with accurate function boundary annotations. We identified several challenging code constructs that represent hard-to-analyze aspects of binary code, and show code examples for each code construct. As part of this discussion, we present new code parsing algorithms in our open source Dyninst tool kit that support these constructs, including a new model for describing jump tables that improves our ability to precisely determine the control flow targets, a new interprocedural analysis to determine when a function is non-returning, and techniques for handling tail calls. We evaluated how various tool kits fare when handling these code constructs with real software as well as test binaries patterned after each challenging code construct we found in real software.

Code authorship information is important for analyzing software quality, performing software forensics, and improving software maintenance. However, current tools assume that the last developer to change a line of code is its author regardless of all earlier changes. This approximation loses important information. We present two new line-level authorship models to overcome this limitation. We first define the repository graph as a graph abstraction for a code repository, in which nodes are the commits and edges represent the development dependencies. Then for each line of code, structural authorship is defined as a sub graph of the repository graph recording all commits that changed the line and the development dependencies between the commits, weighted authorship is defined as a vector of author contribution weights derived from the structural authorship of the line and based on a code change measure between commits, for example, best edit distance. We have implemented our two authorship models as a new git built-in tool git-author. We evaluated git-author in an empirical study and a comparison study. In the empirical study, we ran git-author on five open source projects and found that git-author can recover more information than a current tool (git-blame) for about 10% of lines. In the comparison study, we used git-author to build a line-level model for bug prediction. We compared our line-level model with an existing file-level model. The results show that our line-level model performs consistently better than the file-level model when evaluated on our data sets produced from the Apache HTTP server project.

Large-scale systems typically mount many different file systems with distinct performance characteristics and capacity. Applications must efficiently use this storage in order to realize their full performance potential. Users must take into account potential file replication throughout the storage hierarchy as well as contention in lower levels of the I/O system, and must consider communicating the results of file I/O between application processes to reduce file system accesses. Addressing these issues and optimizing file accesses requires detailed runtime knowledge of file system performance characteristics and the location(s) of files on them. In this paper, we propose Fast Global File Status (FGFS), a scalable mechanism to retrieve file information, such as its degree of distribution or replication and consistency. We use a novel node-local technique that turns expensive, non-scalable file system calls into simple string comparison operations. FGFS raises the namespace of a locally-defined file path to a global namespace with little or no file system calls to obtain global file properties efficiently. Our evaluation on a large multi-physics application shows that most FGFS file status queries on its executable and 848 shared library files complete in 272 milliseconds or faster at 32,768 MPI processes. Even the most expensive operation, which checks global file consistency, completes in under 7 seconds at this scale, an improvement of several orders of magnitude over the traditional checksum technique.

Density-based clustering algorithms are a widely-used class of data mining techniques that can find irregularly shaped clusters and cluster data without prior knowledge of the number of clusters it contains. DBSCAN is the most well-known density-based clustering algorithm. We introduce our version of DBSCAN, called Mr. Scan, which uses a hybrid parallel implementation that combines the MRNet tree-based distribution network with GPGPU-equipped nodes. Mr. Scan avoids the problems of existing implementations by effectively partitioning the point space and by optimizing DBSCAN's computation over dense data regions. We tested Mr. Scan on both a geolocated Twitter dataset and image data obtained from the Sloan Digital Sky Survey. At its largest scale, Mr. Scan clustered 6.5 billion points from the Twitter dataset on 8,192 GPU nodes on Cray Titan in 17.3 minutes. All other parallel DBSCAN implementations have only demonstrated the ability to cluster up to 100 million points.

Visualizing a program's structure and security characteristics is the intrinsic part of in-depth software security assessment. Such an assessment is typically an analyst-driven task. The visualization for security analysis is usually labor-intensive, since analysts need to read documents and source code, synthesize trace data from multiple sources (e.g., system utilities like lsof or strace). To help address this problem, we propose SecSTAR, a tool that dynamically collects the key information from a system and automatically produces the necessary diagrams to support the first steps of widely-used security analysis methodologies, such as Microsoft Threat Modeling and UW/UAB First Principles Vulnerability Assessment (FPVA). SecSTAR uses an efficient dynamic binary instrumentation technique, self-propelled instrumentation, to collect trace data from production systems during runtime then automatically produces diagrams. Furthermore, SecSTAR allows analysts to interactively view and explore diagrams in a web browser. For example, analysts can navigate the diagrams through time and at different levels of detail. We demonstrated the usefulness of using SecSTAR to produce FPVA-style diagrams for a widely used and complex distributed middleware system, the Condor high-throughput scheduling system. Compared with the original manual approach in FPVA, SecSTAR shortened the initial diagram construction time from months to hours and constructed a more accurate diagram visualizing the complete runtime structure of Condor.

Binary instrumentation allows users to inject new code into programs without requiring source code, symbols, or debugging information. Instrumenting a binary requires structural modifications such as moving code, adding new code, and overwriting existing code; these modifications may unintentionally change the program's semantics. Binary instrumenters attempt to preserve the intended semantics of the program by further transforming the code to compensate for these structural modifications. Current instrumenters may fail to correctly preserve program semantics or impose significant unnecessary compensation cost because they lack a formal model of the impact of their structural modifications on program semantics. These weaknesses are particularly acute when instrumenting highly optimized or malicious code, making current instrumenters less useful as tools in the security or high-performance domains. We present a formal specification of how the structural modifications used by instrumentation affect a binary's visible behavior, and have adapted the Dyninst binary instrumenter to use this specification, thereby guaranteeing correct instrumentation while greatly reducing compensation costs. When compared against the fastest widely used instrumenters our technique imposed 46% less overhead; furthermore, we can successfully instrument highly defensive binaries that are specifically looking for code patching and instrumentation.

Program binaries are an artifact of a production process that begins with source code and ends with a string of bytes representing executable code. There are many reasons to want to know the specifics of this process for a given binary---for forensic investigation of malware, to diagnose the role of the compiler in crashes or performance problems, or for reverse engineering and decompilation---but binaries are not generally annotated with such provenance details. Intuitively, the binary code should exhibit properties specific to the process that produced it, but it is not at all clear how to find such properties and map them to specific elements of that process.

The Dyninst binary instrumentation and analysis framework distinguishes itself from other binary instrumentation tools through its abstract, machine independent interface; its emphasis on anywhere, any-time binary instrumentation; and its low overhead that is proportional to the number of instrumented locations. Dyninst represents the program in terms of familiar control flow structures such as functions, loops, and basic blocks, and users manipulate these representations to insert instrumentation anywhere in the binary. We use graph transformation techniques to insure that this instrumentation executes when desired even when instrumenting highly optimized (or malicious) code that other instrumenters cannot correctly instrument. Unlike other binary instrumenters, Dyninst can instrument at any time in the execution continuum, from static instrumentation (binary rewriting) to instrumenting actively executing code (dynamic instrumentation). Furthermore, we allow users to modify or remove instrumentation at any time, with such modifications taking immediate effect. Our analysis techniques allow us to insert new code without modifying uninstrumented code; as a result, all uninstrumented code executes at native speed. We demonstrate that our techniques provide this collection of capabilities while imposing similar or lower overhead than other widely used instrumenters.

Binary code presents unique analysis challenges, particularly when debugging information has been stripped from the executable. Among the valuable information lost in stripping are the identities of standard library functions linked into the executable; knowing the identities of such functions can help to optimize automated analysis and is instrumental in understanding program behavior. Library fingerprinting attempts to restore the names of library functions in stripped binaries, using signatures extracted from reference libraries. Existing methods are brittle in the face of variations in the toolchain that produced the reference libraries and do not generalize well to new library versions. We introduce semantic descriptors, high-level representations of library functions that avoid the brittleness of existing approaches. We have extended a tool, unstrip, to apply this technique to fingerprint wrapper functions in the GNU C library. unstrip discovers functions in a stripped binary and outputs a new binary, with meaningful names added to the symbol table. Other tools can leverage these symbols to perform further analysis. We demonstrate that our semantic descriptors generalize well and substantially outperform existing library fingerprinting techniques.

Many high-performance tools, applications and infrastructures, such as Paradyn, STAT, TAU, Ganglia, SuperMon, Astrolabe, Borealis, and MRNet, use data aggregation to synthesize large data sets and reduce data volumes while retaining relevant information content. Hierarchical or tree-based overlay networks (TBONs) are often used to execute data aggregation operations in a scalable, piecewise fashion. In this paper, we present state compensation, a scalable failure recovery model for high-bandwidth, low-latency TBON computations. By leveraging inherently redundant state information found in many TBON computations, state compensation avoids explicit state replication (for example, process checkpoints and message logging) and incurs no overhead in the absence of failures. Further, when failures do occur, state compensation uses a weak data consistency model and localized protocols that allow processes to recover from failures independently and responsively. Based on a formal specification of our data aggregation model, we have validated state compensation and identified its assumptions and limitations: state compensation requires that data aggregation operations be associative, commutative and idempotent. In this paper, we describe the fundamental state compensation concepts and a prototype implementation integrated into the MRNet TBON infrastructure. Our experiments with this framework suggest that for TBONs supporting up to millions of application processes, state compensation can yield millisecond recovery latencies and inconsequential application perturbation.

We present a novel technique that identifies the source compiler of program binaries, an important element of program provenance. Program provenance answers fundamental questions of malware analysis and software forensics, such as whether programs are generated by similar tool chains; it also can allow development of debugging, performance analysis, and instrumentation tools specific to particular compilers. We formulate compiler identification as a structured learning problem, automatically building models to recognize sequences of binary code generated by particular compilers. We evaluate our techniques on a large set of real-world test binaries, showing that our models identify the source compiler of binary code with over 90 % accuracy, even in the presence of interleaved code from multiple compilers. A case study demonstrates the use of inferred compiler provenance to augment stripped binary parsing, reducing parsing errors by 18%.

Current high-end parallel systems consist of hundreds of thousands of compute cores arranged in a complex hierarchical structure; future systems will have millions of cores. Systems, such as the Altix 4700, Blue Gene, Roadrunner, and Cray XT5, deploy multiple compute cores (homogeneous or heterogeneous) with multiple levels of shared and private caches within a processor, clustered into SMP nodes and coupled via a communication network to large-scale distributed systems. The development of efficient programs is extremely complex since the architectural details are exposed to the programmer. Productive use of such machines requires highly scalable programming tools for debugging, performance analysis, and fault tolerance. In addition, new programming models might significantly facilitate the task of the programmer. This special issue of Concurrency and Computation: Practice and Experience is devoted to programming tools that facilitate the development of efficient programs for such large-scale architectures. It is a collection of the best papers submitted to the international workshop on Scalable Tools for High-end Computing (STHEC 2008) that was held in conjunction with the International Conference on Supercomputing on June 7th on the Greek Island Kos. The papers present state-of-the-art tools for performance analysis and checkpointing on those machines. Performance analysis tools use measurements gathered during the execution of the application to detect portions of the code that can be further improved. Thus, they have to be able to cope with the large number of processors. Tools for checkpointing provide the possibility to restart an application in the case of a system failure; they have to be able to handle large number of cores as well. The selected papers present different techniques for building tools that will scale to thousands of cores. HPCToolkit 1 is a profiling-based performance analysis environment presenting the data in close relation to the source code without requiring an instrumentation of the source code. Scalasca 2 performs a parallel replay of the execution on the application's processors to find performance bottlenecks automatically. The combination of TAU and MRNet 3 provides a scalable infrastructure to offload performance data. Establishing the overlay network requires no added support from the job manager or application. Periscope 4 is based on a network of analysis agents that performs an online analysis of the application's performance behavior. When the application is started, additional processors can be allocated for the analysis agents to scale the analysis. CPPC 5 is a tool for portable checkpointing of message-passing applications. It consists of a runtime library and a compiler that assists the user by performing time-consuming tasks, such as data flow and communications analyses as well as code instrumentation. We would like to thank the authors for their excellent contributions to this special issue. We hope that it inspires future research in tools that support programmers of high-end systems in the development of efficient programs.

Abstract Performance monitoring of HPC applications offers opportunities for adaptive optimization based on the dynamic performance behavior, unavailable in purely post‐mortem performance views. However, a parallel performance monitoring system must have low overhead and high efficiency to make these opportunities tangible. We describe a scalable parallel performance monitor calledTAUoverMRNet (ToM), created from the integration of the TAU performance system and the Multicast Reduction Network (MRNet). The integration is achieved through a plug‐in architecture in TAU that allows the selection of different transport substrates to offload the online performance data. A method to establish the transport overlay structure of the monitor from within TAU, one that requires no added support from the job manager or application, is presented. We demonstrate the distribution of performance analysis from the sink to the overlay nodes and the reduction in the large‐scale profile data that could, otherwise, overwhelm any single sink. The results show low perturbation and significant savings accrued from reduction at large processor‐counts. Copyright © 2009 John Wiley & Sons, Ltd.

Group file operations are a new, intuitive idiom for tools and middleware - including parallel debuggers and runtimes, performance measurement and steering, and distributed resource management - that require scalable operations on large groups of distributed files. The idiom provides new semantics for using file groups in standard file operations to eliminate costly iteration. A file-based idiom promotes conciseness and portability, and eases adoption. With explicit semantics for aggregation of group results, the idiom addresses a key scalability barrier. We have designed TBON-FS, a new distributed file system that provides scalable group file operations by leveraging tree-based overlay networks (TBONs) for scalable communication and data aggregation. We integrated group file operations into several tools: parallel versions of common utilities including cp, grep, rsync, tail, and top, and the Ganglia Distributed Monitoring System. Our experience verifies the group file operation idiom is intuitive, easily adopted, and enables a wide variety of tools to run efficiently at scale.

We present a scalable temporal order analysis technique that supports debugging of large scale applications by classifying MPI tasks based on their logical program execution order. Our approach combines static analysis techniques with dynamic analysis to determine this temporal order scalably. It uses scalable stack trace analysis techniques to guide selection of critical program execution points in anomalous application runs. Our novel temporal ordering engine then leverages this information along with the application's static control structure to apply data flow analysis techniques to determine key application data such as loop control variables. We then use lightweight techniques to gather the dynamic data that determines the temporal order of the MPI tasks. Our evaluation, which extends the Stack Trace Analysis Tool (STAT), demonstrates that this temporal order analysis technique can isolate bugs in benchmark codes with injected faults as well as a real world hang case with AMG2006.

Careless attention to opening files, often caused by problems with path traversal or shared directories, can expose applications to attacks on the file names that they use. In this paper we present criteria to determine if a path is safe from attack and how previous algorithms are not sufficient to protect against such attacks. We then describe an algorithm to safely open a file when in the presence of an attack (and how to detect the presence of such an attack), and provide a new library of file open routines that embodies our algorithm. These routines can be used as one-for-one substitutes for conventional POSIX open and fopen calls.

Parallel performance monitoring extends parallel measurement systems with infrastructure and interfaces for online performance data access, communication, and analysis. At the same time it raises concerns for the impact on application execution from monitor overhead. The application monitoring scheme parameterized by performance events to monitor, access frequency and the type of data analysis operation defines a set of monitoring requirements. The monitoring infrastructure presents its own choices, particularly the amount and configuration of resources devoted explicitly to monitoring. The key to scalable, low-overhead parallel performance monitoring is to match the application monitoring demands to the effective operating range of the monitoring system (or vice-versa). A poor match can result in over-provisioning (wasted resources) or in under-provisioning (lack of scalability, high overheads and poor quality of performance data). We present a methodology and evaluation framework to determine the sweet-spots for performance monitoring using TAU and MRNet.

Many tools that target parallel and distributed environments must co-locate a set of daemons with the distributed processes of the target application. However, efficient and portable deployment of these daemons on large scale systems is an unsolved problem. We overcome this gap with LaunchMON, a scalable, robust, portable, secure, and general purpose infrastructure for launching tool daemons. Its API allows tool builders to identify all processes of a target job, launch daemons on the relevant nodes and control daemon interaction. Our results show that LaunchMON scales to very large daemon counts and substantially enhances performance over existing ad hoc mechanisms.

Petascale systems will present several new challenges to performance and correctness tools. Such machines may contain millions of cores, requiring that tools use scalable data structures and analysis algorithms to collect and to process application data. In addition, at such scales, each tool itself will become a large parallel application - already, debugging the full Blue-Gene/L (BG/L) installation at the Lawrence Livermore National Laboratory requires employing 1664 tool daemons. To reach such sizes and beyond, tools must use a scalable communication infrastructure and manage their own tool processes efficiently. Some system resources, such as the file system, may also become tool bottlenecks. In this paper, we present challenges to petascale tool development, using the stack trace analysis tool (STAT) as a case study. STAT is a lightweight tool that gathers and merges stack traces from a parallel application to identify process equivalence classes. We use results gathered at thousands of tasks on an Infiniband cluster and results up to 208 K processes on BG/L to identify current scalability issues as well as challenges that will be faced at the petascale. We then present implemented solutions to these challenges and show the resulting performance improvements. We also discuss future plans to meet the debugging demands of petascale machines.

Context sensitive page mappings provide different mappings from virtual addresses to physical page frames depending on whether a memory reference occurs in a data or instruction context. Such differences can be used to modify the behavior of programs that reference their executable code in a data context. Previous work has demonstrated several applications of context sensitive page mappings, including protection against buffer-overrun attacks and circumvention of self-checksumming codes. We extend context sensitive page mappings to the virtual machine monitor, allowing operation independent of the guest operating system. Our technique takes advantage of the VMM's role in enforcing protection between guest operating systems to interpose on guest OS memory management operations and selectively introduce context sensitive page mappings.

We present the Stack Trace Analysis Tool (STAT) to aid in debugging extreme-scale applications. STAT can reduce problem exploration spaces from thousands of processes to a few by sampling stack traces to form process equivalence classes, groups of processes exhibiting similar behavior. We can then use full-featured debuggers on representatives from these behavior classes for root cause analysis. STAT scalably collects stack traces over a sampling period to assemble a profile of the application's behavior. STAT routines process the samples to form a call graph prefix tree that encodes common behavior classes over the program's process space and time. STAT leverages MRNet, an infrastructure for tool control and data analyses, to overcome scalability barriers faced by heavy-weight debuggers. We present STAT's design and an evaluation that shows STAT gathers informative process traces from thousands of processes with sub-second latencies, a significant improvement over existing tools. Our case studies of production codes verify that STAT supports the quick identification of errors that were previously difficult to locate.

Abstract Profiling is a key technique for achieving high performance. Call‐path profiling is a refinement of this technique that classifies a function's behavior based on the path taken to reach the function. This information is particularly useful when optimizing programs that use libraries, such as those for communication (MPI or PVM), linear algebra (ScaLAPACK), or threading. We present a new method for call‐path profiling called incremental call‐path profiling. We profile only a subset of the functions in the program, allowing the use of more complex metrics while lowering the overhead. This combination of call‐path information and complex metrics is particularly useful for localizing bottlenecks in frequently called functions. We also describe the implementation and application of iPath, an incremental call‐path profiler. iPath was used to profile two real‐world applications: the MILC su3_rmd QCD distributed simulation and the Paradyn instrumentation daemon. In both applications we found and removed call‐path‐specific bottlenecks. Our modifications to su3_rmd reduced the running time of the program from 3001 to 1652 s, a 45% decrease. Our modifications to the Paradyn instrumentation daemon greatly increased its efficiency. The time required to instrument our benchmark program was reduced from 296 to 6.4 s, a 98% decrease. Copyright © 2006 John Wiley & Sons, Ltd.

Abstract We implemented a simple multilevel feedback queue scheduler in the Linux 2.6 kernel and compared its response to interactive tasks with that of the new Linux 2.6 scheduler. Our objectives were to evaluate whether Linux 2.6 accomplished its goal of improved interactivity, and to see whether a simpler model could do as well without all of the special cases and exceptions that the new Linux 2.6 scheduler acquired. We describe the two algorithms in detail, report their average interactive response times under different kinds of background workloads, and compare their methods of deciding whether a task is interactive. The MLFQ scheduler performs comparably to the Linux 2.6 scheduler in all response time tests and displays some inadvertent improvements in turnaround time, while avoiding the complex task of explicitly defining interactivity. We maintain an inverse relationship between priority and time slice length, and this seems to be the primary reason that the MLFQ remains simple, yet performs comparably to the Linux 2.6 scheduler. These results may provide some guidelines for designers of new scheduling systems. Copyright © 2006 John Wiley & Sons, Ltd.

Before performing pattern matching, a typical misuse-NIDS performs protocol analysis: it parses network traffic according to the attack protocol and normalizes the traffic into the form used by its signatures. For example, consider a NIDS that attempts to identify an HTTP-based attack. The NIDS must extract the URL from the raw traffic, convert HEX encoded characters into their equivalent ASCII form if necessary, and only then perform matching on the normalized URL. Protocol analysis is time consuming, especially in a NIDS that analyzes and normalizes all traffic just to discover that the majority of the traffic does not match any of its signatures.We develop a technique called protomatching that combines protocol analysis, normalization, and pattern matching into a single phase. The goal of the protomatching signatures is to exclude non-attack traffic quickly before the NIDS performs any further time-consuming analysis. Protomatching is based on a novel signature with two properties. First, the signature ensures that the attack pattern appears in the context that enables successful attack. This saves the need for protocol analysis. Second, the signature matches both encoded and normalized forms of an attack and this saves the need for normalization.We empirically show that a Snort implementation that uses protomatching is up to 49% faster than an unmodified Snort.

An attack mutation algorithm takes a known instance of an attack and transforms it into many distinct instances by repeatedly applying attack transformations. Such algorithms are widely used for testing intrusion detection systems. We investigate the notion of completeness of a mutation algorithm: its capability to generate all possible attack instances from a given set of attack transformations. We define the notion of a Phi-complete mutation algorithm. Given a set of transformations Phi, an algorithm is complete with respect to Phi, if it can generate every instance that the transformations in Phi derive. We show that if the rules in Phi are uniform and reversible then a Phi-complete algorithm exists. Intuitively speaking, uniform and reversible transformations mean that we can first exclusively apply transformations that simplify the attack, then exclusively apply transformations that complicate it, and still get all possible instances that are derived by the rules in Phi. Although uniformity and reversibility may appear severe restrictions, we show that common attack transformations are indeed uniform and reversible. Therefore, our Phi-complete algorithm can be incorporated into existing testing tools for intrusion detection systems. Furthermore, we show that a Phi-complete algorithm is useful, not only for testing purposes, but also for determining whether two packet traces are two different mutations of the same attack

The increasing availability of high-performance computing systems with thousands, tens of thousands, and even hundreds of thousands of computational nodes is driving the demand for programming models and infrastructures that allow effective use of such large-scale environments. Tree-based overlay networks (TBO~Ns) have proven to provide such a model for distributed tools like performance profilers, parallel debuggers, system monitors and system administration tools. We demonstrate that the extensibility and flexibility of the TBO~N distributed computing model, along with its performance characteristics, make it surprisingly general, particularly for applications outside the tool domain. We describe many interesting applications and commonly-used algorithms for which TBO~Ns are well-suited and provide a new (non-tool) case study, a distributed implementation of the mean-shift algorithm commonly used in computer vision to delineate arbitrarily shaped clusters in complex, multi-modal feature spaces.

Performance analysis tools are critical for the effective use of large parallel computing resources, but existing tools have failed to address three problems that limit their scalability: (1) management and processing of the volume of performance data generated when monitoring a large number of application processes, (2) communication between a large number of tool components, and (3) presentation of performance data and analysis results for applications with a large number of processes. In this paper, we present a novel approach for finding performance problems in applications with a large number of processes that leverages our multicast and data aggregation infrastructure to address these three performance tool scalability barriers. First, we show how to design a scalable, distributed performance diagnosis facility. We demonstrate this design with an on-line,

We describe a new approach for locating the causes of anomalies in distributed systems. Our target environment is a distributed application that contains multiple identical processes performing similar activities. We use a new, lightweight form of dynamic instrumentation to collect function-level traces from each process. If the application fails, the traces are automatically compared to each other. We find anomalies by identifying processes that stopped earlier than the rest (sign of a fail-stop problem) or processes that behaved different from the rest (sign of a non-fail-stop problem). Our algorithm does not require reference data to distinguish anomalies from normal behaviors. However, it can make use of such data when available to reduce the number of false positives. Ultimately, we identify a function that is likely to explain the anomalous behavior. We demonstrated the efficacy of our approach by finding two problems in a large distributed cluster environment called SCore.

Abstract The Linux operating system is quickly becoming a standard, attracting a wide user community and supporting a broad variety of applications and devices. Other vendors, such as Sun, have provided Linux‐compatible system call interfaces to their kernels, but are constrained by the lack of device support. To address this problem, we present a system (called PITS) to build device drivers, in this case for Solaris x86, from Linux source code. To accomplish this goal, we designed tools and Linux kernel emulation code to handle the myriad incompatibilities. These incompatibilities require the ability to resolve symbol conflicts, emulate internal Linux kernel data structures, handle module initialization, and generate module dependencies. With our method, we show that converting Linux device drivers is possible, but has a few technical difficulties. Issues arise with sparse documentation, external user interfaces, and modular driver implementations. There are also fundamental differences between the two operating systems, such as interrupt and DMA handling. We describe each of these issues and their current solutions to build a functional driver in the Solaris environment. Using the IOzone file system benchmark, we also demonstrate comparable performance between our generated SCSI driver set and their corresponding native counterparts. Copyright © 2006 John Wiley & Sons, Ltd.

We present a methodology to automatically construct robust signatures whose accuracy is based on formal reasoning so it can be systematically evaluated. Our methodology is based on two formal languages that describe different properties of a given attack. The first language, called a session signature, describes temporal relations between the attack events. The second, called an attack invariant, describes semantic properties that hold in any instance of the attack. For example, an invariant may state that a given FTP attack must include a successful FTP login and can be launched only after the FTP representation mode has been set to ASCII. We iteratively eliminate false positives and negatives from an initial session signature by comparing the signature language to the language of the invariant. We developed GARD, a tool for session-signature construction, and used it to construct session signatures for multi-step attacks. We show that a session signature is more accurate than existing signatures.

A common way to elude a signature-based NIDS is to transform an attack instance that the NIDS recognizes into another instance that it misses. For example, to avoid matching the attack payload to a NIDS signature, attackers split the payload into several TCP packets or hide it between benign messages. We observe that different attack instances can be derived from each other using simple transformations. We model these transformations as inference rules in a natural-deduction system. Starting from an exemplary attack instance, we use an inference engine to automatically generate all possible instances derived by a set of rules. The result is a simple yet powerful tool capable of both generating attack instances for NIDS testing and determining whether a given sequence of packets is an attack. In several testing phases using different sets of rules, our tool exposed serious vulnerabilities in Snort - a widely deployed NIDS. Attackers acquainted with these vulnerabilities would have been able to construct instances that elude Snort for any TCP-based attack, any Web-CGI attack, and any attack whose signature is a certain type of regular expression.

Summary form only given. MRNet is an infrastructure that provides scalable multicast and data aggregation functionality for distributed tools. While evaluating MRNet's performance and scalability, we learned several important lessons about benchmarking large-scale, distributed tools and middleware. First, automation is essential for a successful benchmarking effort, and should be leveraged whenever possible during the benchmarking process. Second, micro-benchmarking is invaluable not only for establishing the performance of low-level functionality, but also for design verification and debugging. Third, resource management systems need substantial improvements in their support for running tools and applications together. Finally, the most demanding experiments should be attempted early and often during a benchmarking effort to increase the chances of detecting problems with the tool and experimental methodology.

A key function of a host-based intrusion detection system is to monitor program execution. Models constructed using static analysis have the highly desirable feature that they do not produce false alarms; however, they may still miss attacks. Prior work has shown a trade-off between efficiency and precision. In particular, the more accurate models based upon pushdown automata (PDA) are very inefficient to operate due to non-determinism in stack activity. In this paper, we present techniques for determinizing PDA models. We first provide a formal analysis framework of PDA models and introduce the concepts of determinism and stack-determinism. We then present the VP-Static model, which achieves determinism by extracting information about stack activity of the program, and the Dyck model, which achieves stack-determinism by transforming the program and inserting code to expose program state. Our results show that in run-time monitoring, our models slow execution of our test programs by 1% to 135%. This shows that reasonable efficiency needs not be sacrificed for model precision. We also compare the two models and discover that deterministic PDA are more efficient, although stack-deterministic PDA require less memory.

Run-time tools are crucial to program development. In our desktop computer environments, we take for granted the availability of tools for operations such as debugging, profiling, tracing, checkpointing, and visualization. When programs move into distributed or Grid environments, it is difficult to find such tools. This difficulty is caused by the complex interactions necessary between application program, operating system and layers of job scheduling and process management software. As a result, each run-time tool must be individually ported to run under a particular job management system; for m tools and n environments, the problem becomes an m \times n effort, rather than the hoped-for m + n effort. Variations in underlying operating systems can make this problem even worse. The consequence of this situation is a paucity of tools in distributed and Grid computing environments. In response to the problem, we have analyzed a variety of job scheduling environments and run-time tools to better understand their interactions. From this analysis, we isolated what we believe are the essential interactions between the run-time tool, job scheduler and resource manager, and application program. We are proposing a standard interface, called the Tool Dæmon Protocol (TDP) that codifies these interactions and provides the necessary communication functions. We have implemented a pilot TDP library and experimented with Parador, a prototype using the Paradyn Parallel Performance tools profiling jobs running under the Condor batch-scheduling environment.

We present MRNet, a software-based multicast/reduction network for building scalable performance and system administration tools. MRNet supports multiple simultaneous, asynchronous collective communication operations. MRNet is flexible, allowing tool builders to tailor its process network topology to suit their tool's requirements and the underlying system's capabilities. MRNet is extensible, allowing tool builders to incorporate custom data reductions to augment its collection of built-in reductions. We evaluated MRNet in a simple test tool and also integrated into an existing, real-world performance tool with up to 512 tool back-ends. In the real-world tool, we used MRNet not only for multicast and simple data reductions but also with custom histogram and clock skew detection reductions. In our experiments, the MRNet-based tools showed significantly better performance than the tools without MRNet for average message latency and throughput, overall tool start-up latency, and performance data processing throughput.

Abstract To attack the problem of scalability of performance diagnosis tools with respect to application code size, we have developed the Deep Start search strategy—a new technique that uses stack sampling to augment an automated search for application performance problems. Our hybrid approach locates performance problems more quickly and finds performance problems hidden from a more straightforward search strategy. The Deep Start strategy uses stack samples collected as a by‐product of normal search instrumentation to selectdeep starters, functions that are likely to be application bottlenecks. With priorities and careful control of the search refinement, our strategy gives preference to experiments on the deep starters and their callees. This approach enables the Deep Start strategy to find application bottlenecks more efficiently and more effectively than a more straightforward search strategy. We implemented the Deep Start search strategy in the Performance Consultant, Paradyn's automated bottleneck detection component. In our tests, Deep Start found half of our test applications' known bottlenecks between 32% and 59% faster than the Performance Consultant's current search strategy, and finished finding bottlenecks between 10% and 61% faster. In addition to improving the search time, Deep Start often found more bottlenecks than the call graph search strategy. Copyright © 2003 John Wiley & Sons, Ltd.

We present two systems, reliable sockets (rocks) and reliable packets (racks), that provide transparent network connection mobility using only user- level mechanisms. Each system can detect a connection failure within seconds of its occurrence, preserve the endpoint of a failed connection in a suspended state for an arbitrary period of time, and automatically reconnect, even when one end of the connection changes IP address, with correct recovery of in-flight data. To allow rocks and racks to interoperate with ordinary clients and servers, we introduce a general user-level Enhancement Detection Protocol that enables the remote detection of rocks and racks, or any other socket enhancement system, but does not affect applications that use ordinary sockets. Rocks and racks provide the same functionality but have different implementation models: rocks intercept and modify the behavior of the sockets API by using an interposed library, while racks uses a packet filter to intercept and modify the packets exchanged over a connection. Racks and rocks introduce small throughput and latency overheads that we deem acceptable for the level of mobility and reliability they provide.

Abstract We introduce a new technique for automated performance diagnosis, using the program's callgraph. We discuss our implementation of this diagnosis technique in the Paradyn Performance Consultant. Our implementation includes the new search strategy and new dynamic instrumentation to resolve pointer‐based dynamic call sites at run‐time. We compare the effectiveness of our new technique to the previous version of the Performance Consultant for several sequential and parallel applications. Our results show that the new search method performs its search while inserting dramatically less instrumentation into the application, resulting in reduced application perturbation and consequently a higher degree of diagnosis accuracy. Copyright © 2002 John Wiley & Sons, Ltd.

We show how to determine statically whether it is safe for untrusted machine code to be loaded into a trusted host system.

With the development of dynamic compilers for Java, Java's performance promises to rival that of equivalent C/C++ binary executions. This should ensure that Java will become the platform of choice for ubiquitous Web-based supercomputing. Therefore, being able to build performance tools for dynamically compiled Java executions will become increasingly important. In this paper we discuss those aspects of dynamically compiled Java executions that make performance measurement difficult: (i) some Java application methods may be transformed from byte-code to native code at run-time; (ii) even in native form, application code may interact with the Java virtual machine. We describe Paradyn-J, an experimental version of the Paradyn Parallel Performance Tool that addresses this environment by describing performance data from dynamically compiled executions in terms of the multiple execution forms (interpreted byte-code and directly executed native code) of a method, costs of the dynamic compilation, and costs of residual dependencies of the application on the virtual machine. We use performance data from Paradyn-J to tune a Java application method, and improve its interpreted byte-code execution by 11% and its native form execution by 10%. As a result of tuning just one method, we improve the application's total execution time by 11% when run under Sun's ExactVM (included in the Platform2 release of JDK). The results of our work are a guide to virtual machine designers as to what type of performance data should be available through Java VM performance tool APIs. Copyright © 2000 John Wiley & Sons, Ltd.

Process checkpointing is a basic mechanism required for providing high throughput computing service on distributively owned resources. We present a new process checkpoint and migration technique, called process hijacking, that uses dynamic program re-writing techniques to add checkpointing capability to a running program. Process hijacking makes it possible to checkpoint and migrate proprietary applications that cannot be re-linked with a checkpoint library, and it makes it possible to dynamically hand off an ordinary running process to a distributed resource management system such as Condor. We discuss the problems of adding checkpointing capability to a program already in execution: loading new code into the running process; and replacing functions of the process with calls to dynamically loaded functions. We use the DynInst API process editing library, augmented with a new call for replacing functions, to solve these problems.

The use of threads is becoming commonplace in both sequential and parallel programs. This paper describes our design and initial experience with non-trace based performance instrumentation techniques for threaded programs. Our goal is to provide detailed performance data while maintaining control of instrumentation costs. We have extended Paradyn's dynamic instrumentation (which can instrument programs without recompiling or relinking) to handle threaded programs.Controlling instrumentation costs means efficient instrumentation code and avoiding locks in the instrumentation. Our design is based on low contention data structures. To associate performance data with individual threads, we have all threads share the same instrumentation code and assign each thread with its own private copy of performance counters or timers. The asynchrony in a threaded program poses a major challenge to dynamic instrumentation. To implement time-based metrics on a per-thread basis, we need to instrument thread context switches, which can cause instrumentation code to interleave. Interleaved instrumentation can not only corrupt performance data, but can also cause a scenario we call self-deadlock where an instrumentation code deadlocks a thread. We introduce thread-conscious locks to avoid self-deadlock, and per-thread virtual CPU timers to reduce the chance of interleaved instrumentation accessing the same performance counter or timer, and to reduce the number of expensive timer calls at thread context switches.Our initial implementation is on SPARC Solaris 2.5 and 2.6 including multiprocessor Sun UltraSPARC Enterprise machines. We tested our tool on large multithreaded applications, including the Java Virtual Machine (JVM). We show how our new techniques helped us to speed up a Java graphics native method by 42% and consequently increase by 24% the amount of work that can be done in unit time in a game applet.

Accurate performance diagnosis of parallel and distributed programs is a difficult and time-consuming task. We describe a new technique that uses historical performance data, gathered in previous executions of an application, to increase the effectiveness of automated performance diagnosis. We incorporate several different types of historical knowledge about the application's performance into an existing profiling tool, the Paradyn Parallel Performance Tool. We gather performance and structural data from previous executions of the same program, extract knowledge useful for diagnosis from this collection of data in the form of search directives, then input the directives to an enhanced version of Paradyn, which conducts a directed online diagnosis. Compared to existing approaches, incorporating historical data shortens the time required to identify bottlenecks, decreases the amount of unhelpful instrumentation, and improves the usefulness of the information obtained from a diagnostic se...

This paper describes a new approach to finding performance bottlenecks in shared-memory parallel programs and its embodiment in the Paradyn Parallel Performance Tools running with the Blizzard fine-grain distributed shared memory system. This approach exploits the underlying system's cache coherence protocol to detect data sharing patterns that indicate potential performance bottlenecks and presents performance measurements in a data-centric manner. As a demonstration, Parodyn helped us improve the performance of a new shared-memory application program by a factor of four.

The development of a high-performance parallel system or application is an evolutionary process. It may begin with models or simulations, followed by an initial implementation of the program. The code is then incrementally modified to tune its performance and continues to evolve throughout the applications's life span. At each step, the key question for developers is: how and how much did the performance change? This question arises comparing an implementation to models or simulations; considering versions of an implementation that use a different algorithm, communication or numeric library, or language; studying code behavior by varying number or type of processors, type of network, type of processes, input data set or work load, or scheduling algorithm; and in benchmarking or regression testing. Despite the broad utility of this type of comparison, no existing performance tool provides the necessary functionality to answer it; even state of the art research tools such as Paradyn[2] and Pablo[3] focus instead on measuring the performance of a single program execution.

Programs written inhigh-level parallel languages need profiling tools that provide performance data in terms of the semantics of the high-level language.But high-level performance data can be incomplete when the cause of a performance problem camot be explained in terms of the semantics of the language.We also need the ability to view the performance of the underlying mechanisms used by the language and correlate the underlying activity to the language source code.The key techniques for providing these performance views is the ability to map low-level performance data up to the language abstractions.We describe how we use this information to produce performance data at the higher levels, and how we present this data in terms of both the code and parallel data structures.We have developed an implementation of these mapping techniques for the data parallel CM Fortran language running on the TMC CM-5.We have augmented the Paradyn Parallel Performance TOOIS with these mapping and high-level language facilities and used them to study several real data parallel Fortran (CM Fortran) applications.1 :[NTRODUCTION High-level parallel languages offer portable, concise notations for specifying parallel programs, and their compilers automatically map programs onto complex parallel machines.These languages can free programmers from the difficult, error-prone, and sometimes ineffective task of specifying parallel computations explicitly.We describe a tool for profiling the performance of parallel prc,grams written with a high-level parallel language or library.Thn paper concentrates on the mechanisms for mapping low-level performance data to the high-level language control and data struc-Tlrk work is supported in pan by Wright Laboratory Avionics Dkectorate, Air Force Matenaf Command, USAF, under grarrt F33615-94-1-1525 (ARPA order no.B550), arrd CDA-90246 18, arrd Department of Energy Grant DE-FG02-93ER25 176.

The parallel scientific computing community is placing increasing emphasis on portability and scalability of programs, languages, and architectures. This creates new challenges for developers of parallel performance analysis tools, who will have to deal with increasing volumes of performance data drawn from diverse platforms. One way to meet this challenge is to incorporate sophisticated facilities for data interpretation and experiment planning within the tools themselves, giving them increased flexibility and autonomy in gathering and selecting performance data. This panel discussion brings together four research groups that have made advances in this direction.

Massively parallel processors have begun using commodity operating systems that support demand paged virtual memory. To evaluate the utility of virtual memory, we measured the behavior of seven shared memory parallel application programs on a simulated distributed shared memory machine. Our results: confirm the importance of gang CPU scheduling; show that a page faulting processor should spin rather than invoice a parallel context switch; show that our parallel programs frequently touch most of their data; and indicate that memory, not just CPUs, must be "gang scheduled". Overall, our experiments demonstrate that demand paging has limited value on current parallel machines because of the applications' synchronization and memory reference patterns and the machines' high page fault and parallel context switch overheads.>

Today's global internetworks challenge the ability of name services and other information services to locate data quickly. The authors introduce distributed active catalog and meta-data caching for optimizing queries in this environment. The active catalog constrains the search space for a query by returning a list of data repositories where the answer to the query is likely to be found. Meta-data caching improves performance by keeping frequently used characterizations of the search space close to the user, and eliminating active catalog communication and processing costs. When searching for query responses, the techniques contact only the small percentage of the data repositories with actual responses, resulting in search times of a few seconds. A distributed active catalog and meta-data caching method was implemented in a prototype descriptive name service called Nomenclator. Performance results for Nomenclator in a search space of 1000 data repositories are presented.>

Performance monitoring of large scale parallel computers creates a dilemma: we need to collect detailed information to find performance bottlenecks, yet collecting all this data can introduce serious data collection bottlenecks. At the same time, users are being inundated with volumes of complex graphs and tables that require a performance expert to interpret. We present a new approach called the W3 Search Model, that addresses both these problems by combining dynamic on-the-fly selection of what performance data to collect with decision support to assist users with the selection and presentation of performance data. We present a case study describing how a prototype implementation of our technique was able to identify the bottlenecks in three real programs. In addition, we were able to reduce the amount of performance data collected by a factor ranging from 13 to 700 compared to traditional sampling and trace based instrumentation techniques.

The global Intemet provides users with an informa-tion labyrinth- rich in resourees, yet confusing and difficult to navigate. Many researchers are responding with a desire to integrate all ~es, indeed all information,

The authors present a novel technique, called true zeroing, that permits direct, quantitative, and fair comparison of parallel program performance metrics. This technique was applied to three programs that include both numeric and symbolic applications. Three existing metrics, Gprof, Critical Path, and Quartz/NPT, and several new variations were compared. The result of this comparison was that while Critical Path provided the best overall guidance, it was not universally better than the other metrics. Because there is no single universal metric, future parallel performance systems need to support multiple metrics. The authors present a set of recommendations to tool builders based on the experience gained during this case study.>

A techinque for tracing and replaying message-passing programs for debugging is presented. The technique is optimal in the common case and has good performance in the worst case. By making runtime tracing decisions, only a fraction of the total number of messages is traced, gaining two orders of magnitude reduction over traditional techniques which trace every message. Experiments indicate that only 1% of the messages often need to be traced. These traces are sufficient to provide replay, allowing an execution to be reproduced any number of times for debugging. This work is novel in that runtime decisions are used to detect and trace only those messages that introduce nondeterminacy. With the proposed strategy, large reductions in trace size allow long-running programs to be replayed that were previously unmanageable. In addition, the reduced tracing experiments alleviate tracing bottlenecks, allowing executions to be debugged with substantially lower execution-time overhead.>

For shared-memory systems, the most commonly assumed programmer's model of memory is sequential consistency. The weaker models of weak ordering, release consistency with sequentially consistent synchronization operations, data-race-free-0, and data-race-free-1 provide higher performance by guaranteeing sequential consistency to only a restricted class of programs - mainly programs that do not exhibit data races. To allow programmers to use the intuition and algorithms already developed for sequentially consistent systems, it is important to determine when a program written for a weak system exhibits no data races. In this paper, we investigate the extension of dynamic data race detection techniques developed for sequentially consistent systems to weak systems. A potential problem is that in the presence of a data race, weak systems fail to guarantee sequential consistency and therefore dynamic techniques may not give meaningful results. However, we reason that in practice a weak system...

The IPS-2 parallel program measurement tools pro-vide performance data from application programs, the operating system, hardware, network, and other sources. Previous versions of IPS-2 allowed programmers to collect information about an application based only on what could be collected by software instrumentation inserted into the program (and system call libraries). We have developed an open interface, called the “external time histogram”, pro-viding a graceful way to include external data from many sources. The user can tell IPS-2 of new sources of perfor-mance data through an extensible metric description language. The data from these external sources is automat-ically collected when the application program is run. IPS-2 provides a library to simplify constructing the external data collectors. The new version of IPS-2 can measure shared-memory and message-passing parallel programs running on a heterogeneous collection of machines. Data from C or Fortran programs, and data from simulations ean be pro-cessed by the same tool. As a result of including the new external performance data, IPS-2 now can report on a whole new set of performance problems. We describe the results of using IPS-2 on two real applications: a shared-memory database join utility, and a multi-processor interconnection network simulator. Even though these applications previously went through careful tuning, we were able to precisely identify performance problems and extract additional performance improvements of about 30%.

For shared-memory parallel programs that use explicit synchronization, data race detection is an important part of debugging. A data race exists when concurrently executing sections of code access common shared variables. In programs intended to be data race free, they are sources of nondeterminism usually considered bugs. Previous methods for detecting data races in executions of parallel programs can determine when races occurred, but can report many data races that are artifacts of others and not direct manifestations of program bugs. Artifacts exist because some races can cause others and can also make false races appear real. Such artifacts can overwhelm the programmer with information irrelevant for debugging. This paper presents results showing how to identify nonartifact data races by validation and ordering. Data race validation attempts to determine which races involve events that either did execute concurrently or could have (called feasible data races). We show how each de...

Nomenclator is an architecture for providing efficient descriptive (attribute-based) naming in a large internet environment. As a test of the basic design, we have built a Nomenclator prototype that uses X.500 as its underlying data repository. X.500 SEARCH queries that previously took several minutes, can, in many cases, be answered in a matter of seconds. Our system improves descriptive query performance by trimming branches of the X.500 direetory tree from the search. These tree-trimming techniques are part of an active catalog that constrains the search space as needed during query processing. The active catalog provides information about the data distribution (meta-&ta) to constrain query processing on demand. Nomenclator caches both data (responses to querim) and meta-data (data distribution information, tree-trimming techniques, data access techniques) to speed future queries. Nomenclator relieves users of the need to understand the structure of the name space to locate objects quickly in a large, structured name environment. Nomenclator is a meta-level service that will eventually incorporate other name services in addition to X.500. Its techniques for improving performance should be generally applicable to other naming systems.

Flowback analysis is a powerful technique for debugging programs.It allows the programmer to examine dynamic dependence in a program's execution history without having to reexecute the program.The goal is to present to the programmer a graphical view of the dynamic program dependence.We are building a system, called PPD, that performs flowback analysis while keeping the execution time overhead low.We also extend the semantics of flowback analysis to parallel programs.This paper describes details of the graphs and algorithms needed to implement efficient flowback analysis for parallel programs.Execution-time overhead is kept low by recording only a small amount of trace during a program's execution.We use semantic analysis and a technique called incremental tracing to keep the time and space overhead low.As part of the semantic analysis, PPD uses a static program dependence graph structure that reduces the amount of work done at compile time and takes advantage of the dynamic information produced during execution time.Parallel programs have been accommodated in two ways.First, the flowback dependence can span process boundaries; that is, the most recent modification to a variable might be traced to a different process than that one that contains the current reference.The static dynamic program dependence graphs of the individual processes are tied together with synchronization and data dependence information to form complete graphs that represent the entire program.Second, our algorithms will detect potential data-race conditions in the access to shared variables.The programmer can be directed to the cause of the race condition.PPD is currently being implemented for the C programming language on a Sequent Symmetry shared-memory .

IPS, a performance measurement system for parallel and distributed programs, is currently running on its second implementation. IPS's model of parallel programs uses knowledge about the semantics of a program's structure to provide two important features. First, IPS provides a large amount of performance data about the execution of a parallel program, and this information is organized so that access to it is easy and intuitive. Secondly, IPS provides performance analysis techniques that help to guide the programmer automatically to the location of program bottlenecks. The first implementation of IPS was a testbed for the basic design concepts, providing experience with a hierarchical program and measurement model, interactive program analysis, and automatic guidance techniques. It was built on the Charlotte distributed operating system. The second implementation, IPS-2, extends the basic system with new instrumentation techniques, an interactive and graphical user interface, and new automatic guidance analysis techniques. This implementation runs on 4.3BSD UNIX systems, on the VAX, DECstation, Sun 4, and Sequent Symmetry multiprocessor.>

Large internet environments are increasing the difficulty of network management. Integrating increasing numbers of autonomous subnetworks (each with an increasing number of hosts) makes it more difficult to determine if the network managers of the subnetworks will interoperate correctly. We propose a high level, formal specification language, NMSL, as an aid in solving this problem. NMSL has two aspects of operation, a descriptive aspect and a prescriptive aspect. In its descriptive aspect, NMSL specifies abstractions of the network components and their instantiations, and verifies the consistency of such a specification. The abstractions include the data objects and processes in a network management system. These abstractions are instantiated on network elements. Network elements are grouped together in the specification of domains of administration. An extension mechanism is provided to allow for the specification of new management characteristics that the basic language cannot express. In its prescriptive aspect, NMSL generates configuration information directly from a consistent specification. This information is used to configure network management processes to make their operation consistent with their specifications. Standard management protocols (such as the emerging ISO or IETF standards) can be used to incorporate the configuration information into running management processes.

Novel approaches are presented for designing performance measurement systems for parallel and distributed programs. The first approach involves unifying performance information into a single, regular structure that reflects the structure of programs under measurement. The authors define a hierarchical model for the execution of parallel and distributed programs as a framework for the performance measurement. A complete different levels of detail in the hierarchy. The second approach is based on the development of automatic guidance techniques that can direct users to the location of performance problems in the program. Guidance information from such techniques supplies facts about problems in the program and provides possible answers for the further improvement of program efficiency. A performance measurement system, called IPS, has been developed as a prototype of the authors' model and design. Some of the test results from IPS are also discussed.>

Procedure calls provide a synchronous interface to call downward through successive layers of abstraction, and remote procedure calls allow the layers to reside in different address spaces. A design is given for distributed upcalls, a mechanism for propagating upcalls across address space boundaries. Distributed upcalls provide a natural complement to remote procedure calls, allowing the user to arbitrarily place abstractions in the server or in the client. A server structuring system called CLAM, which is currently being used to support an extensible window management system, is presented. The CLAM system, including distributed upcalls, remote procedure call extensions to C++, dynamic loading, and basic window classes, is currently running under 4.3BSD Unix on Microvax workstations.>

Interactive debugging requires that the programmer be able to half a program at interesting points in its execution. The authors define distributed breakpoints and present an algorithm for implementing the detection points and an algorithm for halting a distributed program in a consistent state. Events that can be partially ordered are defined as detectable and form the basis for the breakpoint predicates. From the breakpoint definition, an algorithm is obtained that can be used in a distributed debugger to detect these breakpoints. The halting algorithm extends K.M. Chandy and L. Lamport's (1985) algorithm for recording global state and solves the problem of processes that are not fully connected or frequently communicating.>

The authors present the design, implementation, and testing of the critical path analysis technique using the IPS performance measurement tool for parallel and distributed programs. They create a precedence graph of a program's activities (program activity graph) with the data collected during the execution of a program. The critical path, the longest path in the program activity graph, represents the sequence of the program activities that take the longest time to execute. Various algorithms are developed to track the critical path from this graph. The events in this path are associated with the entities in the source program, and the statistical results are displayed on the basis of the hierarchical structure of the IPS. The test results from the measurement of sample programs show that the knowledge of the critical path in a program's execution helps users identify performance problems and better understand the behavior of a program.>

This paper addresses the design and implementation of an integrated debugging system for parallel programs running on shared memory multi-processors (SMMP). We describe the use of flowback analysis to provide information on causal relationships between events in a program's execution without re-executing the program for debugging. We introduce a mechanism called incremental tracing that, by using semantic analyses of the debugged program, makes the flowback analysis practical with only a small amount of trace generated during execution. We extend flowback analysis to apply to parallel programs and describe a method to detect race conditions in the interactions of the co-operating processes.

A framework for measuring the performance of distributed programs is presented. This framework includes a model of distributed programs, a description of the measurement principles and methods, and a guideline for implementing these ideas. The author describes a measurement system called the Distributed Programs Monitor (DPM), which he has constructed on the basis of these concepts. DPM has been implemented and used for measurement studies on two different operating systems, DEMOS/MP and Berkeley Unix.>

CLAM is an object-oriented system designed to support the building of extensible graphical user interfaces. CLAM provides a basic windowing environment with the ability to extend its functions using dynamically loaded C++ classes. The dynamically loaded classes allow for performance tuning (by transparently loading the class in either the client or the CLAM server) and for sharing of new functions.

Abstract The DEMOS/MP operating system has moved from a supercomputer with a simple addressing structure to a network of microcomputers. This transformation was done without significant changes to the semantics of the original DEMOS, i.e. existing DEMOS programs should run on DEMOS/MP. The changes to DEMOS were simplified by the structure of its primitive objects and the functions over those objects. The structure of DEMOS links and processes were the major contributors to the simplicity. The changes made to produce DEMOS/MP involved the internal structure of link, modification to parts of the kernel, and limited changes to the various system processes.

Abstract Writing and debugging distributed programs can be difficult. When a program is working, it can be difficult to achieve reasonable execution performance. A major cause of these difficulties is a lack of tools for the programmer. We use a model of distributed computation and measurement to implement a program monitoring system for programs running on the Berkeley UNIX 4.2BSD operating system. The model of distributed computation describes the activities of the processes within a distributed program in terms of computation (internal events) and communication (external events). The measurement model focuses on external events and separates the detection of external events, event record selection and data analysis. The implementation of the measurement tools involved changes to the Berkeley UNIX kernel, and the addition of daemon processes to allow the monitoring activity to take place across machine boundaries. A user interface has also been implemented.

Process migration has been added to the DEMOS/MP operating system. A process can be moved during its execution, and continue on another processor, with continuous access to all its resources. Messages are correctly delivered to the process's new location, and message paths are quickly updated to take advantage of the process's new location. No centralized algorithms are necessary to move a process.