Microfluidic networks can be applied to droplet-based Lab-on-a-Chip devices, where droplets are used to confine samples which flow through closed microchannels along different paths in order to execute (bio-)chemical experiments. In order to allow this routing of droplets, the design of the microfluidic network has to be precisely defined and afterward fabricated. However, neither the fabrication process nor the applied materials and components are perfect and, therefore, the fabricated microfluidic device frequently contains defects (produced by fabrication tolerances, properties of the used material, or fluctuation of supply pumps). Those may have a severe impact on the behavior of the microfluidic network and can even render the network useless. Furthermore, these defects complicate the design process, which eventually results in a “trial-and-error”-approach causing high costs with respect to time and money. Consequently, designers want to anticipate how robust their design is against those defects. This article, for the first time, describes how these defects can be abstracted, which eventually allows to evaluate the robustness already in the design process. We additionally introduce models considering single and multiple defects as well as corresponding methods for their analysis. Evaluations on a microfluidic network which is used to screen drug compounds confirm that the resulting robustness analysis indeed provides designers with a simple metric to decide how sensitive their design is against defects. The models and methods proposed in this article are grounded on the established 1-D analysis model.

Droplet-based microfluidic devices are a well-established and highly potential Labs-on-Chip technology as droplets are especially suited to encapsulate biological samples like cells, proteins, or DNA. These droplets are injected in a continuous phase and flow through closed microchannels to modules executing operations on the droplets-eventually realizing a (bio-)chemical experiment. Moreover, this technology even allows for the realization of multiple experiments on a single device by letting droplets take different paths through the microfluidic network. This requires, however, a mechanism to route the droplets along these paths. To this end, the concept of passive droplet routing has been suggested which entirely avoids complex valves or switches and, instead, realizes the routing by exploiting the hydrodynamic effect that a droplet will always flow along the path with the highest volumetric flow rate. Since droplets themselves affect the volumetric flow rate, a dedicated sequence of droplets can define what path is taken and, hence, what experiment is executed. However, determining such a droplet sequence is a nontrivial task, as it is nonobvious how much droplets are needed, when to inject them, and how they are interacting. In this paper, we are addressing this issue by providing, for the first time, an automatic method for the generation of droplet sequences realizing the desired experiments on a given network. Evaluations confirm the practicability of the proposed solution. Moreover, the suitability of the obtained droplet sequences is additionally validated through simulations on the 1D analysis model.

Due to the ever increasing complexity of modern circuits and systems, verification represents one of the most time-consuming tasks in the entire design process for embedded systems. For this purpose, simulation-based techniques are widely applied in industrial contexts. Here, stimuli are determined which are used as input for the Design under Verification (DUV) and are supposed to trigger different aspects of the new design. However, usually much more stimuli are generated than actually needed to comprehensively cover all aspects. This obviously increases the run time of the verification significantly. Consequently, verification engineers aim for minimizing the number of stimuli after their generation - without loosing their coverage. Existing solutions, however, usually generate results which are far from being optimal. Besides that, their scalability is severely limited. In this work, we propose a solution for an exact minimization of stimuli. To this end, we utilize the computational power of modern reasoning engines such as MAX-SAT solvers which can efficiently minimize a given set of stimuli. Experimental evaluations confirm that, compared to previous work, up to 63% further reduction can be obtained and scalability significantly increases.

Understanding variability is essential to allow the configuration of software systems to diverse requirements. Variability-aware program analysis techniques have been proposed for analyzing the space of program variants. Such techniques are highly beneficial, e.g., to determine the potential impact of changes during maintenance. This article presents an interprocedural and configuration-aware change impact analysis (CIA) approach for determining the possibly impacted source code elements when changing the source code of a product family. The approach also supports engineers, who are adapting the code of specific product variants after an initial pre-configuration. The approach can be adapted to work with different variability mechanisms, it is more precise than existing CIA approaches, and it can be implemented using standard control flow and data flow analysis. We report evaluation results on the benefit and performance of the approach using industrial product lines.

The complexity of droplet microfluidics grows with the implementation of parallel processes and multiple functionalities on a single device. This poses a severe challenge to the engineer designing the corresponding microfluidic networks. In today’s design processes, the engineer relies on calculations, assumptions, simplifications, as well as his/her experiences and intuitions. To validate the obtained specification of the microfluidic network, usually a prototype is fabricated and physical experiments are conducted thus far. In case the design does not implement the desired functionality, this prototyping iteration is repeated—obviously resulting in an expensive and time-consuming design process. To avoid unnecessary debugging loops involving fabrication and testing, simulation methods could help to initially validate the specification of the microfluidic network before any prototype is fabricated. However, state-of-the-art simulation tools come with severe limitations, which prevent their utilization for practically relevant applications. More precisely, they are often not dedicated to droplet microfluidics, cannot handle the required physical phenomena, are not publicly available, and can hardly be extended. In this work, we present an advanced simulation approach for droplet microfluidics that addresses these shortcomings and, eventually, allows simulating practically relevant applications. To this end, we propose a simulation framework at the one-dimensional analysis model, which directly works on the specification of the design, supports essential physical phenomena, is publicly available, and is easy to extend. Evaluations and case studies demonstrate the benefits of the proposed simulator: While current state-of-the-art tools were not applicable for practically relevant microfluidic networks, the proposed simulator allows reducing the design time and costs, e.g., of a drug screening device from one person month and USD 1200, respectively, to just a fraction of that.

Two-phase flow microfluidics is a sophisticated and frequently applied Labs-on-Chip (LoC) technology as they allow to automatically conduct medical/biochemical experiments. In this technology, small volumes of reagents, so-called droplets, flow in an immiscible continuous flow inside closed channels making it particularly biocompatible. In the recent past, this technology was extended by a concept allowing to passively navigate droplets through the system-leading to so-called Networked Labs-on-Chips (NLoCs). After the design of an NLoC architecture which defines the comprising connectivity between components and, by this, how the considered medical/biochemical experiments are supposed to be realized, the question remains how to properly dimension the used components, i.e. especially how to dimension the used channels. However, this is a challenging task which is conducted manually thus far and frequently leads to specifications that do not work as intended. In this paper, we are addressing this issue by providing the designer with methods that allow to 1) automatically validate whether a chosen specification of an NLoC indeed works as intended and 2) automatically dimension NLoCs. Case studies demonstrate the importance and usefulness of the proposed methods for determining proper specifications of NLoCs.

In the domain of microfluidic devices, a paradigm shift from application-specific to fully-programmable solutions takes place (a similar development from ASICS to FPGAs has been observed in conventional circuitry). So-called Programmable Microfluidic Devices (PMDs) provide a promising platform in this regard. Here, fluids can be pushed into various reaction vessels whose inflow and outflow is controlled by valves. The regular structure in combination with the flexibility of defining various flow paths through valves allows to realize a vast range of biological or chemical applications by only changing the corresponding valve-control sequence. However, determining a sound valve-control constitutes a non-trivial task. Although first automatic approaches for this problem have recently been proposed, we show that they frequently yield impractical control sequences. In this work, we address this issue by providing a precise definition of the underlying design task. Afterwards, we present complementary solutions (both exact as well as heuristic) and discuss how they guarantee a sound valve-control. Experimental evaluations demonstrate that the proposed solutions are capable of automatically generating a sound valve-control for PMDs.

Feature models are frequently used to capture the knowledge about configurable software systems and product lines. However, feature modeling of large-scale systems is challenging as models are needed for diverse purposes. For instance, feature models can be used to reflect the perspectives of product management, technical solution architecture, or product configuration. Furthermore, models are required at different levels of granularity. Although numerous approaches and tools are available, it remains hard to define the purpose, scope, and granularity of feature models. This paper first reports results and experiences of an exploratory case study on developing feature models for two large-scale industrial automation software systems. We report results on the characteristics and modularity of the feature models, including metrics about model dependencies. Based on the findings from the study, we developed FORCE, a modeling language, and tool environment that extends an existing feature modeling approach to support models for different purposes and at multiple levels, including mappings to the code base. We demonstrate the expressiveness and extensibility of our approach by applying it to the well-known Pick and Place Unit example and an injection molding subsystem of an industrial product line. We further show how our approach supports consistency between different feature models. Our results and experiences show that considering the purpose and level of features is useful for modeling large-scale systems and that modeling dependencies between feature models is essential for developing a system-wide perspective.

Labs-on-Chips (LoCs) implement laboratory procedures on a single chip and are successfully used for chemical and biomedical applications. A promising and emerging realization of such chips are Networked LoCs (NLoCs) in which small volumes of fluids, so-called droplets, flow in closed channels of submillimeter diameters. NLoCs allow for an incubation and storage of assays over a long period of time and, hence, avoid evaporation and unwanted reactions. To increase the flexibility, effectiveness, and reusability, network functionalities allow to passively route droplets in channels and, hence, to dynamically select operations depending on the executed experiment. However, only manually designed architectures are considered for NLoCs thus far. They frequently suffer from large execution times and/or a high contamination of channels. To overcome these drawbacks, we propose the consideration of application-specific architectures for NLoCs. To this end, an automatic design method is proposed which, for a given set of experiments as well as constraints and objectives from the designer, is able to generate an optimized NLoC architecture realizing these experiments. Evaluations and case studies demonstrate the potential of the proposed solution for design exploration. Moreover, we are able to show that application-specific architectures are capable of realizing experiments in just a fraction of the time needed by architectures used thus far as well as with a substantially reduced contamination.

Continuous-flow microfluidics rapidly evolved in the last decades as a solution to automate laboratory procedures in molecular biology and biochemistry. Therefore, the physical design of the corresponding chips, i.e., the placement and routing of the involved components and channels, received significant attention. Recently, several physical design solutions for this task have been presented. However, they often rely on general heuristics which traverse the search space in a rather arbitrary fashion and, additionally, consider placement and routing independently from each other. Consequently, the obtained results are often far from being optimal. In this work, a methodology is proposed which aims for determining close-to-optimal physical designs for continuous-flow microfluidic biochips. To this end, we consider all - or, at least, as much as possible - of the valid solutions. As this obviously yields a significant complexity, solving engines are utilized to efficiently traverse the search space and pruning schemes are proposed to reduce the search space without discarding too many promising solutions. Evaluations show that the proposed methodology is capable of determining optimal results for small experiments to be realized. For larger experiments, close-to-optimal results can efficiently be derived. Moreover, compared to the current state-of-the-art, improvements of up to 1-2 orders of magnitude can be observed.

Digital microfluidics is an emerging technology that provide fluidic-handling capabilities on a chip. One of the most important issues to be considered when conducting experiments on the corresponding biochips is the routing of droplets. A recent variant of biochips uses a micro-electrode-dot-array (MEDA) which yields a finer controllability of the droplets. Although this new technology allows for more advanced routing possibilities, it also poses new challenges to corresponding CAD methods. In contrast to conventional microfluidic biochips, droplets on MEDA biochips may move diagonally on the grid and are not bound to have the same shape during the entire experiment. In this work, we present an exact routing method that copes with these challenges while, at the same time, guarantees to find the minimal solution with respect to completion time. For the first time, this allows for evaluating the benefits of MEDA biochips compared to their conventional counterparts as well as a quality assessment of previously proposed routing methods in this domain.

Labs-on-Chip integrate and minimize the functionality of complete conventional laboratories on a single chip. An upcoming and especially biocompatible realization are Networked Labs-on-Chips (NLoCs). In NLoCs, small volumes of reagents, so-called droplets, flow in an immiscible fluid in closed channels. An external pump applies a force to this immiscible fluid driving the droplets through the channels of the NLoC. However, the exact flow behavior of droplets in NLoCs physically depends on many factors and interdependencies. This makes it cumbersome to manually determine the taken path of a droplet and the time it needs to pass the NLoC. For the same reason, also almost no automated design solutions exist for NLoCs yet. In this work, we present a discrete model enabling designers and design automation tools to efficiently determine the droplets' path and positions. The precision of the proposed model is evaluated by a systematic examination for basic building blocks of NLoCs as well as for a complete architecture. The resulting model can be used for manual inspections of the droplets' behavior in an NLoC and, additionally, provides the basis for automated design solutions.

Labs-on-Chips (LoCs) revolutionize conventional biochemical processes and may even replace laboratories by integrating and minimizing their functionalities on a single chip. In a promising and emerging realization of LoCs, small volumes of reagents, so-called droplets, transport the biological sample and flow in closed channels of sub-millimeter diameters. This realization is called Networked Labs-on-Chips (NLoCs). The architecture of an NLoC defines different paths through which the droplets can flow. These paths are realized by splitting channels into multiple successor channels - so-called bifurcations. However, whether the architecture indeed allows to route droplets along the desired paths and, hence, correctly executes the intended experiment is not guaranteed. In this work, we present the first automatic solution for verifying whether an NLoC architecture allows to correctly route the droplets. Our evaluations demonstrate the applicability and importance of the proposed solution on a set of NLoC architectures.

On a droplet-based Labs-on-Chip (LoC) device, tiny volumes of fluids, so-called droplets, flow in channels of micrometer scale. The droplets contain chemical/biological samples that are processed by different modules on the LoC. In current solutions, an LoC is a single-purpose device that is designed for a specific application, which limits its flexibility. In order to realize a multi-purpose system, different modules are interconnected in a microfluidic network — yielding so-called Networked LoCs (NLoCs). In NLoCs, the droplets are routed to the desired modules by exploiting hydrodynamic forces. A well established topology for NLoCs are ring networks. However, the addressing schemes provided so far in the literature only allow to address multiple modules by re-injecting the droplet at the source every time, which is a very complex task and increases the risk of ruining the sample. In this work, we address this issue by revising the design of the network nodes, which include the modules. A novel configuration allows the droplet to undergo processing several times in cascade by different modules with a single injection. Simulating the trajectory of the droplets across the network confirmed the validity of our approach.

Static code analysis techniques are widely and successfully used for mainstream programming languages. However, domain-specific languages and company-specific variations of languages often lack the same level of support. An example is the domain of industrial automation, where programmable logic controller programs are mainly written in languages conforming to the IEC 61131-3 standard, a non-mainstream family of languages. This experience paper reports about the development of a program analysis framework for the IEC 61131-3 languages. We use OMG's Abstract Syntax Tree Meta-Model (ASTM) as an abstract representation and show our extensions of this model to represent the different IEC 61131-3 languages. Using this representation our approach generates Jimple code, an intermediate representation used by the Soot program analysis framework. We use Soot's standard analysis methods to compute a system dependence graph, which is then used for change impact analysis. We apply our approach to industrial-size product lines of our industry partner to demonstrate its correctness and performance. Finally, we discuss experiences and lessons learned intended for developers of program analysis methods for nonmainstream languages.

Understanding variability is essential to allow the configuration of software systems to diverse requirements. Variability-aware program analysis techniques have been proposed for analyzing the space of program variants. Such techniques are highly beneficial, e.g., to determine the potential impact of changes during maintenance. This paper presents an interprocedural and configuration-aware change impact analysis (CIA) approach for determining possibly impacted products when changing source code of a product family. The approach further supports engineers, who are adapting specific product variants after an initial pre-configuration. The approach can be adapted to work with different variability mechanism, it provides more precise results than existing CIA approaches, and it can be implemented using standard control flow and data flow analysis. Using an industrial product line we report evaluation results on the benefit and performance of the approach.

Dynamic program analysis is a technique which records a program execution for the purpose of analyzing its behavior and building high-level models and views. This paper presents an approach to build a high-level model of the behavior of a PLC program component as observed in a program execution. Based on a deterministic record and replay technique, a model is synthesized which represents the transition behavior, timing information, and input output behavior of the component. Then this model can be used to check other executions of the same or similar programs for compliance with the model. We present the synthesis techniques and two variants of trace analysis algorithms.

Application engineers frequently create customer-specific products in two stages: the required software components are first selected to create an initial product which is then evolved by refining the selected features and adapting the code to meet the customers' requirements. For instance, developers frequently set configuration options in the code to adjust the product. However, given that such changes are often necessary in the entire code base it is hard to know which part of the code is still relevant for the chosen configuration options. This means that engineers need to understand and maintain a lot of code that is potentially inactive in a particular product variant. Existing approaches provide only partial solutions: for instance, feature-to-code mappings do not adequately consider complex code dependencies of the implemented features. Static analysis techniques provide better results but usually do not consider variability aspects. We present an approach to automatically identify inactive code in product variants using a configuration-aware code analysis technique. We demonstrate the flexibility of our approach by customizing it to a product line of an industry partner in the domain of industrial automation. We further evaluate the approach to demonstrate its effectiveness, accuracy, and performance.