Publications
2010 |
Schneider, Sigurd; Beschastnikh, Ivan; Chernyak, Slava; Ernst, Michael D.; Brun, Yuriy Synoptic: Summarizing system logs with refinement Proceedings Article In: Proceedings of the Workshop on Managing Systems via Log Analysis and Machine Learning Techniques (SLAML), Vancouver, Canada, 2010. @inproceedings{Schneider10,Distributed systems are often difficult to debug and understand. A typical way of gaining insight into system behavior is by inspecting its execution logs. Manual inspection of logs is arduous, and few tools can analyze an arbitrary system log out of the box. To support this task we developed Synoptic. Synoptic outputs a concise graph representation of logged events that captures important temporal event invariants mined from the log. We applied Synoptic to synthetic and real distributed system logs, and found that it augmented a distributed system designer's understanding of system behavior with reasonable overhead for an offline analysis tool. Synoptic makes no assumptions about the system, and requires no system modifications. In contrast to prior approaches, Synoptic uses a combination of refinement and coarsening instead of just coarsening to explore the space of representations. Additionally, it infers temporal event invariants to capture distributed system semantics that are often present in system logs. These invariants drive the exploration process and are preserved in the final representation. |
Malek, Sam; Edwards, George; Brun, Yuriy; Tajalli, Hossein; Garcia, Joshua; Krka, Ivo; Medvidovic, Nenad; Mikic-Rakic, Marija; Sukhatme, Gaurav An architecture-driven software mobility framework Journal Article In: Journal of Systems and Software, vol. 83, no. 6, pp. 972–989, 2010. @article{Malek10,Software architecture has been shown to provide an appropriate level of granularity for assessing a software system's quality attributes (e.g., performance and dependability). Similarly, previous research has adopted an architecture-centric approach to reasoning about and managing the run-time adaptation of software systems. For mobile and pervasive software systems, which are known to be innately dynamic and unpredictable, the ability to assess a system's quality attributes and manage its dynamic run-time behavior is especially important. In the past, researchers have argued that a software architecture-based approach can be instrumental in facilitating mobile computing. In this paper, we present an integrated architecture-driven framework for modeling, analysis, implementation, deployment, and run-time migration of software systems executing on distributed, mobile, heterogeneous computing platforms. In particular, we describe the framework's support for dealing with the challenges posed by both logical and physical mobility. We also provide an overview of our experience with applying the framework to a family of distributed mobile robotics systems. This experience has verified our envisioned benefits of the approach, and has helped us to identify several avenues of future work. |
Brun, Yuriy Improving impact of self-adaptation and self-management research through evaluation methodology Proceedings Article In: Proceedings of Software Engineering for Adaptive and Self-Managing Systems (SEAMS), pp. 1–9, Cape Town, South Africa, 2010. @inproceedings{Brun10seams,Today, self-adaptation and self-management approaches to software engineering are viewed as specialized techniques and reach a somewhat limited community. In this paper, I overview the current state and expectation of self-adaptation and self-management impact in industry and in premier publication venues and identify what we, as a community, may do to improve such impact. In particular, I find that common evaluation methodologies make it relatively simple for self-adaptation and self-management research to be compared to other such research, but not to more-traditional software engineering research. I argue that extending the evaluation to include comparisons to traditional software engineering techniques may improve a reader's ability to judge the contribution of the research and increase its impact. Finally, I propose a set of evaluation guidelines that may ease the promotion of self-adaptation and self-management as mainstream software engineering techniques. |
Krka, Ivo; Brun, Yuriy; Popescu, Daniel; Garcia, Joshua; Medvidovic, Nenad Using dynamic execution traces and program invariants to enhance behavioral model inference Proceedings Article In: Proceedings of the New Ideas and Emerging Results Track at the 32nd International Conference on Software Engineering (ICSE), pp. 179–182, Cape Town, South Africa, 2010. @inproceedings{Krka10icse-nier,Software behavioral models have proven useful for design, validation, verification, and maintenance. However, existing approaches for deriving such models sometimes overgeneralize what behavior is legal. We outline a novel approach that utilizes inferred program invariants and method invocation sequences to obtain an object-level model to describe legal execution sequences. The key insight is using program invariants to identify similar states in the sequences. We exemplify how our approach improves upon certain aspects of the state-of-the-art FSA-inference techniques. |
2009 |
Cheng, Betty H. C.; Lemos, Rogério; Giese, Holger; Inverardi, Paola; Magee, Jeff; Andersson, Jesper; Becker, Basil; Bencomo, Nelly; Brun, Yuriy; Cukic, Bojan; Serugendo, Giovanna Di Marzo; Dustdar, Schahram; Finkelstein, Anthony; Gacek, Cristina; Geihs, Kurt; Grassi, Vincenzo; Karsai, Gabor; Kienle, Holger M.; Kramer, Jeff; Litoiu, Marin; Malek, Sam; Mirandola, Raffaela; Müller, Hausi A.; Park, Sooyong; Shaw, Mary; Tichy, Matthias; Tivoli, Massimo; Weyns, Danny; Whittle, Jon Software engineering for self-adaptive systems: A research roadmap Book Section In: Cheng, Betty H. C.; Lemos, Rogério; Giese, Holger; Inverardi, Paola; Magee, Jeff (Ed.): Software Engineering for Self-Adaptive Systems, vol. 5525, pp. 1–26, Springer-Verlag, 2009, ISBN: 978-3-642-02160-2. @incollection{Cheng09,The goal of this roadmap paper is to summarize the state-of-the-art and to identify critical challenges for the systematic software engineering of self-adaptive systems. The paper is partitioned into four parts, one for each of the identified essential views of self-adaptation: modelling dimensions, requirements, engineering, and assurances. For each view, we present the state-of-the-art and the challenges that our community must address. This roadmap paper is a result of the Dagstuhl Seminar 08031 on ``Software Engineering for Self-Adaptive Systems,'' which took place in January 2008. |
Krka, Ivo; Brun, Yuriy; Edwards, George; Medvidovic, Nenad Synthesizing partial component-level behavior models from system specifications Proceedings Article In: Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE), pp. 305–314, Amsterdam, The Netherlands, 2009. @inproceedings{Krka09fse,Initial system specifications, such as use-case scenarios and properties, only partially specify the future system. We posit that synthesizing partial component-level behavior models from these early specifications can improve software development practices. In this paper, we provide a novel algorithm for deriving a Modal Transition System (MTS) for individual system components from system-level scenario and property specifications. These generated MTSs capture the possible component implementations that (1) necessarily provide the behavior required by the scenarios, (2) restrict behavior forbidden by the properties, and (3) leave the behavior that is neither explicitly required nor forbidden as undefined. We also show how our algorithm helps discover potential design flaws. |
Brun, Yuriy; Medvidovic, Nenad Crystal-growth-inspired algorithms for computational grids Proceedings Article In: Proceedings of the Workshop on Bio-Inspired Algorithms for Distributed Systems (BADS), pp. 19–26, Barcelona, Spain, 2009, ISBN: 978-1-60558-584-0. @inproceedings{Brun09bads,Biological systems surpass man-made systems in many important ways. Most notably, systems found in nature are typically self-adaptive and self-managing, capable of surviving drastic changes in their environments, such as internal failures and malicious attacks on their components. Large distributed software systems have requirements common to those of some biological systems, particularly in the number and power of individual components and in the qualities of service of the system. However, it is not immediately clear how engineers can extract useful properties from natural systems and inject them into software systems. In this paper, we explore the nature's process of crystal growth and develop mechanisms inspired by that process for designing large distributed computational grid systems. The result is the tile architectural style, a set of design principles for building distributed software systems that solve complex computational problems. Systems developed using the tile style scale well to large computations, tolerate faults and malicious attacks, and preserve the privacy of the data. |
Krka, Ivo; Edwards, George; Brun, Yuriy; Medvidovic, Nenad From system specifications to component behavioral models Proceedings Article In: Proceedings of the New Ideas and Emerging Results Track at the 31st International Conference on Software Engineering (ICSE), pp. 315–318, Vancouver, Canada, 2009. @inproceedings{Krka09icse-nier,Early system specifications, such as use-case scenarios and properties, are rarely complete. Partial models of system-level behavior, derived from these specifications, have proven useful in early system analysis. We believe that the scope of possible analyses can be enhanced by component-level partial models. In this paper, we outline an algorithm for deriving a component-level Modal Transition System (MTS) from system-level scenario and property specifications. The generated MTSs capture the possible component implementations that (1) necessarily provide the behavior required by the scenarios, (2) restrict behavior forbidden by the properties, and (3) leave the behavior that is neither explicitly required nor forbidden as undefined. We discuss how these generated models can help discover system design flaws, support requirements elicitation, and help select off-the-shelf components. |
Brun, Yuriy; Reishus, Dustin Path finding in the tile assembly model Journal Article In: Theoretical Computer Science, vol. 410, no. 15, pp. 1461–1472, 2009, ISSN: 0304-3975. @article{Brun09path-finding,Swarm robotics, active self-assembly, and amorphous computing are fields that focus on designing systems of large numbers of small, simple components that can cooperate to complete complex tasks. Many of these systems are inspired by biological systems, and all attempt to use the simplest components and environments possible, while still being capable of achieving their goals. The canonical problems for such biologically-inspired systems are shape assembly and path finding. In this paper, we demonstrate path finding in the well-studied tile assembly model, a model of molecular self-assembly that is strictly simpler than other biologically-inspired models. As in related work, our systems function in the presence of obstacles and can be made fault-tolerant. The path-finding systems use $Theta(1)$ distinct components and find minimal-length paths in time linear in the length of the path. |
Brun, Yuriy; Reishus, Dustin Connecting the dots: Molecular machinery for distributed robotics Journal Article In: Lecture Notes on Computer Science, vol. 5347/2009, pp. 102–111, 2009. @article{Brun09dna-lncs,Nature is considered one promising area to search for inspiration in designing robotic systems. Some work in swarm robotics has tried to build systems that resemble distributed biological systems and inherit biology's fault tolerance, scalability, dependability, and robustness. Such systems, as well as ones in the areas of active self-assembly and amorphous computing, typically use relatively simple components with limited computation, memory, and computational power to accomplish complex tasks such as forming paths in the presence of obstacles. We demonstrate that such tasks can be accomplished in the well-studied tile assembly model, a model of molecular self-assembly that is strictly simpler than other biologically-inspired models. Our systems use a small number of distinct components to find minimal-length paths in time linear in the length of the path while inheriting scalability and fault tolerance of the underlying natural process of self-assembly. |
Brun, Yuriy; Serugendo, Giovanna Di Marzo; Gacek, Cristina; Giese, Holger; Kienle, Holger; Litoiu, Marin; Müller, Hausi; Pezzè, Mauro; Shaw, Mary Engineering self-adaptive systems through feedback loops Book Section In: Cheng, Betty H. C.; Lemos, Rogério; Giese, Holger; Inverardi, Paola; Magee, Jeff (Ed.): Software Engineering for Self-Adaptive Systems, vol. 5525, pp. 48–70, Springer-Verlag, 2009, ISBN: 978-3-642-02160-2. @incollection{Brun09SEfSAS,To deal with the increasing complexity of software systems and uncertainty of their environments, software engineers have turned to self-adaptivity. Self-adaptive systems are capable of dealing with a continuously changing environment and emerging requirements that may be unknown at design-time. However, building such systems cost-effectively and in a predictable manner is a major engineering challenge. In this paper, we explore the state-of-the-art in engineering self-adaptive systems and identify potential improvements in the design process. Our most important finding is that in designing self-adaptive systems, the feedback loops that control self-adaptation must become first-class entities. We explore feedback loops from the perspective of control engineering and within existing self-adaptive systems in nature and biology. Finally, we identify the critical challenges our community must address to enable systematic and well-organized engineering of self-adaptive and self-managing software systems. |
2008 |
Brun, Yuriy Reducing tileset size: 3-SAT and beyond Proceedings Article In: Proceedings of the 14th International Meeting on DNA Computing (DNA), pp. 178, Prague, Czech Republic, 2008. @inproceedings{Brun08dna-sat,In self-assembly research, reducing the number of distinct tiles necessary to compute functions can make it feasible to implement tile systems to solve complex problems. Existing methods for solving 3-SAT, a well-known NP-complete problem, in the tile assembly model involve either using $Theta(n^2)$ distinct tiles to nondeterministically decide whether an $n$-variable Boolean formula is satisfiable or simulating a cellular automata system simulating a Turing machine, which requires a constant but large number of tiles to deterministically make the decision. Here, I propose a system that solves k-SAT nondeterministically, for all $k in mathbbN$, in time linear in the input size using only 64 distinct tiles. Further, I propose a mechanism for converting the tilesets of tile systems for many NP-complete and other problems from tilesets whose size depends on the input into $Theta(1)$-size tilesets. |
Brun, Yuriy University of Southern California, 2008, ISBN: 978-0-549-60920-9. @phdthesis{Brun08PhD,When engineers compare biological and software systems, the former come out ahead in the majority of dimensions. For example, the human body is far more complex, better suited to deal with faulty components, more resistant to malicious agents such as viruses, and more adaptive to environmental changes than your favorite operating system. Thus it follows that we, the engineers, may be able to build better software systems than the ones we build today by borrowing technologies from nature and injecting them into our system design process. In this dissertation, I present an architectural style and accompanying implementation support for building distributed software systems that allow large networks, such as the Internet, to solve computationally intensive problems. This architectural style, the tile style, is based on a nature's system of crystal growth, and thus inherits some of nature's dependability, fault and adversary tolerance, scalability, and security. The tile style allows one to distribute computation onto a large network in a way that guarantees that unless someone controls a large fraction of the network, they cannot learn the private data within the computation or force the computation to fail. These systems are highly scalable, capable of dealing with faulty and malicious nodes, and are discreet since every sufficiently small group of nodes knows neither the problem nor the data. The tile style is based on a formal mathematical model of self-assembly. In order to leverage this model to build software, I define the notion of self-assembling computation and develop systems that compute functions such as adding, multiplying, factoring, and solving NP-complete problems SubsetSum and SAT. For each system, I prove its correctness, compute its probability of successful computation, and show that its running time and tileset size are asymptotically optimal. I use the mathematical nature of the tile assembly model to present a formal mathematical analysis of the tile style, proving that software systems built using this style are discreet, fault- and adversary-tolerant, and scalable. I further implement a tile-style system and use it to distribute computation to empirically evaluate the tile style's utility. |
Brun, Yuriy Solving NP-complete problems in the tile assembly model Journal Article In: Theoretical Computer Science, vol. 395, no. 1, pp. 31–46, 2008, ISSN: 0304-3975. @article{Brun08np-c,Formalized study of self-assembly has led to the definition of the tile assembly model, a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the Internet. Previously, I defined deterministic and nondeterministic computation in the tile assembly model and showed how to add, multiply, and factor. Here, I extend the notion of computation to include deciding subsets of the natural numbers, and present a system that decides $mathitSubsetSum$, a well known NP-complete problem. The computation is nondeterministic and each parallel assembly executes in time linear in the input. The system requires only a constant number of different tile types: 49. I describe mechanisms for finding the successful solutions among the many parallel assemblies and explore bounds on the probability of such a nondeterministic system succeeding and prove that probability can be made arbitrarily close to 1. |
Brun, Yuriy Nondeterministic polynomial time factoring in the tile assembly model Journal Article In: Theoretical Computer Science, vol. 395, no. 1, pp. 3–23, 2008, ISSN: 0304-3975. @article{Brun08factor,Formalized study of self-assembly has led to the definition of the tile assembly model. Previously, I presented ways to compute arithmetic functions, such as addition and multiplication, in the tile assembly model: a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the Internet. Here, I present tile assembly model systems that factor numbers nondeterministically using $Theta(1)$ distinct components. The computation takes advantage of nondeterminism, but theoretically, each of the nondeterministic paths is executed in parallel, yielding the solution in time linear in the size of the input, with high probability. I describe mechanisms for finding the successful solutions among the many parallel executions and explore bounds on the probability of such a nondeterministic system succeeding and prove that probability can be made arbitrarily close to 1. |
Brun, Yuriy Solving satisfiability in the tile assembly model with a constant-size tileset Journal Article In: Journal of Algorithms, vol. 63, no. 4, pp. 151–166, 2008, ISSN: 0196-6774. @article{Brun08sat,Biological systems are far more complex and robust than systems we can engineer today. One way to increase the complexity and robustness of our engineered systems is to study how biological systems function. The tile assembly model is a highly distributed parallel model of nature's self-assembly. Previously, I defined deterministic and nondeterministic computation in the tile assembly model and showed how to add, multiply, factor, and solve $mathitSubsetSum$. Here, I present a system that decides satisfiability, a well-known NP-complete problem. The computation is nondeterministic and each parallel assembly executes in time linear in the input. The system requires only a constant number of different tile types: $64$, an improvement over previously best known system that uses $Theta(n^2)$ tile types. I describe mechanisms for finding the successful solutions among the many parallel assemblies and explore bounds on the probability of such a nondeterministic system succeeding and prove that probability can be made arbitrarily close to $1$. |
Brun, Yuriy Building biologically-inspired self-adapting systems Proceedings Article In: Cheng, Betty H. C.; Lemos, Rogério; Giese, Holger; Inverardi, Paola; Magee, Jeff (Ed.): Proceedings of the Schloss Dagstuhl seminar 08031: Software Engineering for Self-Adaptive Systems, Dagstuhl, Germany, 2008, ISSN: 1862-4405. @inproceedings{Brun08dagstuhl,Biological systems are far more complex than systems we design and build today. The human body alone has orders of magnitude more complexity than our most-intricate designed systems. Further, biological systems are decentralized in such a way that allows them to benefit from built-in error-correction, fault tolerance, and scalability. It follows that if we can extract certain properties of biological systems and inject them into our software design process, we may be able to build complex self-adaptive software systems. Biological systems' complexity makes them not only desirable to guide software design, but also difficult to fully understand. Thus one approach to building software similar to biological systems is by first building models of biology that we can understand. Then these models can guide the high-level design, or architecture of the software systems, resulting in systems that retain the model's fault tolerance, scalability, and other properties. I present a general outline of how one might use biology to create a model to guide the architecture of a software system, and develop one such model and the resulting architectural style, the tile style, for computational systems that can use a large distributed network of computers, such as the Internet, to solve computationally-intensive problems in a discreet, fault-tolerant, and scalable manner. |
Brun, Yuriy Constant-size tileset for solving an NP-complete problem in nondeterministic linear time Journal Article In: Lecture Notes on Computer Science, vol. 4848/2008, pp. 26–35, 2008, ISSN: 0302-9743. @article{Brun08dna-lncs,The tile assembly model, a formal model of crystal growth, is of special interest to computer scientists and mathematicians because it is universal. Therefore, tile assembly model systems can compute all the functions that computers compute. In this paper, I formally define what it means for a system to nondeterministically decide a set, and present a system that solves an NP-complete problem called $mathitSubsetSum$. Because of the nature of NP-complete problems, this system can be used to solve all NP problems in polynomial time, with high probability. While the proof that the tile assembly model is universal implies the construction of such systems, those systems are in some sense ``large'' and ``slow.'' The system presented here uses $49 = Theta(1)$ different tiles and computes in time linear in the input size. I also propose how such systems can be leveraged to program large distributed software systems. |
2007 |
Brun, Yuriy; Medvidovic, Nenad Fault and adversary tolerance as an emergent property of distributed systems' software architectures Proceedings Article In: Proceedings of the 2nd International Workshop on Engineering Fault Tolerant Systems (EFTS), pp. 38–43, Dubrovnik, Croatia, 2007. @inproceedings{Brun07efts,Fault and adversary tolerance have become not only desirable but required properties of software systems because mission-critical systems are commonly distributed on large networks of insecure nodes. In this paper, we describe how the tile style, an architectural style designed to distribute computation, can inject fault and adversary tolerance. The result is a notion of tolerance that is entirely abstracted away from the functional properties of the software system. The client may specify what fraction of the network is faulty or malicious (e.g., $25%$) and the acceptable system failure rate (e.g., $2^-10$), and the system's architecture adjusts automatically to ensure a failure rate no higher than the one specified. The technique is entirely automated and consists of a ``smart redundancy'' mechanism that brings the failure rate exponentially close to $0$ by slowing down the execution speed linearly. |
Brun, Yuriy Arithmetic computation in the tile assembly model: Addition and multiplication Journal Article In: Theoretical Computer Science, vol. 378, no. 1, pp. 17–31, 2007, ISSN: 0304-3975. @article{Brun07arith,Formalized study of self-assembly has led to the definition of the tile assembly model. Research has identified two issues at the heart of self-assembling systems: the number of steps it takes for an assembly to complete, assuming maximum parallelism, and the minimal number of tiles necessary to assemble a shape. In this paper, I define the notion of a tile assembly system that computes a function, and tackle these issues for systems that compute the sum and product of two numbers. I demonstrate constructions of such systems with optimal $Theta(1)$ distinct tile types and prove the assembly time is linear in the size of the input. |
Brun, Yuriy; Medvidovic, Nenad An architectural style for solving computationally intensive problems on large networks Proceedings Article In: Proceedings of Software Engineering for Adaptive and Self-Managing Systems (SEAMS), Minneapolis, MN, USA, 2007, (SEAMS 2020 Most Influential Paper Award.). @inproceedings{Brun07seams,Large networks, such as the Internet, pose an ideal medium for solving computationally intensive problems, such as NP-complete problems, yet no well-scaling architecture for computational Internet-sized systems exists. We propose a software architectural style for large networks, based on a formal mathematical study of crystal growth that will exhibit properties of (1) discreetness (nodes on the network cannot learn the algorithm or input of the computation), (2) fault-tolerance (malicious, faulty, and unstable nodes may not break the computation), and (3) scalability (communication among the nodes does not increase with network or problem size). |
Brun, Yuriy A discreet, fault-tolerant, and scalable software architectural style for Internet-sized networks Proceedings Article In: Proceedings of the Doctoral Symposium at the 29th International Conference on Software Engineering (ICSE), pp. 83–84, Minneapolis, MN, USA, 2007. @inproceedings{Brun07icse-doc-symp,Large networks, such as the Internet, pose an ideal medium for solving computationally intensive problems, such as NP-complete problems, yet no well-scaling architecture for Internet-sized systems exists. I propose a software architectural style for large networks, based on a formal mathematical study of crystal growth that will exhibit properties of (1) discreetness (nodes on the network cannot learn the algorithm or input of the computation), (2) fault-tolerance (malicious, faulty, and unstable nodes cannot break the computation), and (3) scalability (communication among the nodes does not increase with network or problem size). I plan to evaluate the style both theoretically and empirically for these three properties. |
Brun, Yuriy Adding and multiplying in the tile assembly model Proceedings Article In: Proceedings of the 4th Foundations of Nanoscience: Self-Assembled Architectures and Devices (FNANO), Snowbird, UT, USA, 2007. @inproceedings{Brun07fnano,The tile assembly model, a formal model of crystal growth, is of special interest to computer scientists and mathematicians because it is universal. Therefore, tile assembly model systems can compute all the functions that computers compute. In this paper, I formally define what it means for a system to compute a function deterministically and present systems that add and multiply. While the proof that the tile assembly model is universal implies the construction of such systems, those systems are in some sense ``large'' and ``slow.'' The systems presented here all use $Theta(1)$ different tiles (8 to add and 28 to multiply) and compute in time linear in the input size. |
2006 |
Brun, Yuriy; Gopalkrishnan, Manoj Toward in vivo disease diagnosis and treatment using DNA Proceedings Article In: Proceedings of the 2006 International Conference on Bioinformatics & Computational Biology (BIOCOMP), pp. 182–186, Las Vegas, NV, USA, 2006, ISBN: 1-60132-002-7. @inproceedings{Brun06biocomp,We propose a technique to diagnose and treat individual cells in the human body. A virus-like system delivers a copy of a diagnosis and treatment DNA complex to each cell. The complex determines whether the cell has a specific disease based on the presence or absence of indicator mRNA molecules and, if the diagnosis is positive, releases a proper drug for treatment. As a tool for the diagnosis and treatment system, we develop a DNA implementation of an arbitrary finite state machine. |
2005 |
Reishus, Dustin; Shaw, Bilal; Brun, Yuriy; Chelyapov, Nickolas; Adleman, Leonard Self-assembly of DNA double-double crossover complexes into high-density, doubly connected, planar structures Journal Article In: Journal of the American Chemical Society (JACS), vol. 127, no. 50, pp. 17590–17591, 2005. @article{Reishus05, |
2004 |
Chelyapov, Nickolas; Brun, Yuriy; Gopalkrishnan, Manoj; Reishus, Dustin; Shaw, Bilal; Adleman, Leonard DNA triangles and self-assembled hexagonal tilings Journal Article In: Journal of the American Chemical Society (JACS), vol. 126, no. 43, pp. 13924–13925, 2004. @article{Chelyapov04, |
Brun, Yuriy; Ernst, Michael D. Finding latent code errors via machine learning over programs executions Proceedings Article In: Proceedings of the 26th International Conference on Software Engineering (ICSE), pp. 480–490, Edinburgh, Scotland, 2004. @inproceedings{Brun04icse,This paper proposes a technique for identifying program properties that indicate errors. The technique generates machine learning models of program properties known to result from errors, and applies these models to program properties of user-written code to classify and rank properties that may lead the user to errors. Given a set of properties produced by the program analysis, the technique selects a subset of properties that are most likely to reveal an error. An implementation, the Fault Invariant Classifier, demonstrates the efficacy of the technique. The implementation uses dynamic invariant detection to generate program properties. It uses support vector machine and decision tree learning tools to classify those properties. In our experimental evaluation, the technique increases the relevance (the concentration of fault-revealing properties) by a factor of 50 on average for the C programs, and 4.8 for the Java programs. Preliminary experience suggests that most of the fault-revealing properties do lead a programmer to an error. |
Brun, Yuriy; Gopalkrishnan, Manoj; Reishus, Dustin; Shaw, Bilal; Chelyapov, Nickolas; Adleman, Leonard Building blocks for DNA self-assembly Proceedings Article In: Proceedings of the 1st Foundations of Nanoscience: Self-Assembled Architectures and Devices (FNANO), pp. 2–15, Snowbird, UT, USA, 2004. @inproceedings{Brun04fnano,DNA complexes, like the double crossover, are used as building blocks for the assembly of higher-order structures. Currently, the number of experimentally proven reliable complexes is small. We have begun work on expanding the collection of such complexes. Here we report on our design concepts and initial experiments. In particular, we present experimental evidence of two new complexes: quadruple crossovers and triangles. In principle, quadruple crossovers can be extended to three-dimensional, space-filling lego brick complexes, while triangles are capable of hexagonally tiling the plane. |
2003 |
Brun, Yuriy Software fault identification via dynamic analysis and machine learning Masters Thesis Massachusetts Institute of Technology, Cambridge, MA, USA, 2003. @mastersthesis{Brun03masters,I propose a technique that identifies program properties that may indicate errors. The technique generates machine learning models of run-time program properties known to expose faults, and applies these models to program properties of user-written code to classify and rank properties that may lead the user to errors. I evaluate an implementation of the technique, the Fault Invariant Classifier, that demonstrates the efficacy of the error finding technique. The implementation uses dynamic invariant detection to generate program properties. It uses support vector machine and decision tree learning tools to classify those properties. Given a set of properties produced by the program analysis, some of which are indicative of errors, the technique selects a subset of properties that are most likely to reveal an error. The experimental evaluation over 941,000 lines of code, showed that a user must examine only the 2.2 highest-ranked properties for C programs and 1.7 for Java programs to find a fault-revealing property. The technique increases the relevance (the concentration of properties that reveal errors) by a factor of 50 on average for C programs, and 4.8 for Java programs. |
2002 |
Brun, Yuriy The four-color theorem Journal Article In: Undergraduate Journal of Mathematics, pp. 21–28, 2002. @article{Brun02four-color,In this review paper, I introduce graph theory, and discuss the Four Color Theorem. Then I prove several theorems, including Euler's formula and the Five Color Theorem. |
1997 |
Vekhter, Daniel; Rasin, Alex; Brun, Yuriy Mutual exclusion algorithms in distributed networks Journal Article In: Journal of Student Research, Science and Technology, vol. 2, no. 1, pp. 65–67, 1997. @article{Vekhter97,The problem of mutual exclusion is ever-present in distributed networks. Various algorithms have been suggested as a means to solve the problem. This paper discusses the efficiency of three such algorithms --- Test-and-Set bit, Dijkstra's, and Peterson's. The performance of each of the algorithms depends on the number of competing processes and the length of the remainder section. Our experimental results show which of the three algorithms are the most efficient to use depending on the size of the network and the number of remainder steps. |