Systematic pattern selection using pattern language grammars and design space analysis

Software patterns provide reusable solutions to recurring design problems in a particular context. The software architect or designer must find the relevant patterns and pattern languages that need to be considered, and select the appropriate patterns, as well as the best order to apply them. If the patterns and pattern languages are written by multiple pattern authors, it might be necessary to identify interdependencies and overlaps between these patterns and pattern languages first. Out of the possible multitude of patterns and pattern combinations that might provide a solution to a particular design problem, one fitting solution must be selected. This can only be mastered with a sufficient expertise for both the relevant patterns and the domain in which they are applied. To remedy these issues we provide an approach to support the selection of patterns based on desired quality attributes and systematic design decisions based on patterns. We propose to formalize the pattern relationships in a pattern language grammar and to annotate the grammar with effects on quality goals. In a second step, complex design decisions are analyzed further using the design spaces covered by a set of related software patterns. This approach helps to systematically find and categorize the appropriate software patterns—possibly even from different sources. As a case study of our approach, we analyze patterns from a pattern language for distributed object middleware. Copyright © 2006 John Wiley & Sons, Ltd.     

Model-based problem solving for university timetable validation and improvement

Constraint satisfaction problems can be expressed very elegantly in state-based formal methods such as B. But can such specifications be directly used for solving real-life problems? In other words, can a formal model be more than a design artefact but also be used at runtime for inference and problem solving? We will try and answer this important question in the present paper with regard to the university timetabling problem. We report on an ongoing project to build a curriculum timetable validation tool where we use a formal model as the basis to validate timetables from a student’s perspective and to support incremental modification of timetables. In this article we describe the problem domain, the formalization in B and our approach to execute the formal model in a production system using ProB.     

Verifying security protocols with PVS: widening the rank function approach

To enable the verification of authentication protocols, Schneider formulated the rank function approach which could be used, under suitable circumstances, to verify protocols modelled using the process algebra CSP. We develop this theoretical result and extend it to a practical framework which can be used to model and analyse a wider variety of security protocols with respect to a wider range of security specifications than were hitherto possible. These results are achieved using PVS, which also provides tool support for the rank function approach.     

Formal validation of domain-specific languages with derived features and well-formedness constraints

Despite the wide range of existing tool support, constructing a design environment for a complex domain-specific language (DSL) is still a tedious task as the large number of derived features and well-formedness constraints complementing the domain metamodel necessitate special handling. Such derived features and constraints are frequently defined by declarative techniques (such graph patterns or OCL invariants). However, for complex domains, derived features and constraints can easily be formalized incorrectly resulting in inconsistent, incomplete or ambiguous DSL specifications. To detect such issues, we propose an automated mapping of EMF metamodels enriched with derived features and well-formedness constraints captured as graph queries in EMF-IncQuery or (a subset of) OCL invariants into an effectively propositional fragment of first-order logic which can be efficiently analyzed by back-end reasoners. On the conceptual level, the main added value of our encoding is (1) to transform graph patterns of the EMF-IncQuery framework into FOL and (2) to introduce approximations for complex language features (e.g., transitive closure or multiplicities) which are not expressible in FOL. On the practical level, we identify and address relevant challenges and scenarios for systematically validating DSL specifications. Our approach is supported by a tool, and it will be illustrated on analyzing a DSL in the avionics domain. We also present initial performance experiments for the validation using Z3 and Alloy as back-end reasoners.     

MEdit4CEP-CPN: An approach for complex event processing modeling by prioritized colored petri nets

Complex Event Processing (CEP) is an event-based technology that allows us to process and correlate large data streams in order to promptly detect meaningful events or situations and respond to them appropriately. CEP implementations rely on the so-called Event Processing Languages (EPLs), which are used to implement the specific event types and event patterns to be detected for a particular application domain. To spare domain experts this implementation, the MEdit4CEP approach provides them with a graphical modeling editor for CEP domain, event pattern and action definition. From these graphical models, the editor automatically generates a corresponding Esper EPL code. Nevertheless, the generated code is syntactically but not semantically validated. To address this problem, MEdit4CEP is extended in this paper by Prioritized Colored Petri Net (PCPN) formalism, resulting in the MEdit4CEP-CPN approach. This approach provides both a novel PCPN domain-specific modeling language and a graphical editor. By using model transformations, event pattern models can be automatically transformed into PCPN models, and then into the corresponding PCPN code executable by CPN Tools. In addition, by using PCPNs we can compare the expected output with the actual output and can even conduct a quantitative analysis of the scenarios of interest. To illustrate our approach, we have conducted an air quality level detection case study and we show how this novel approach facilitates the modeling, simulation, analysis and semantic validation of complex event-based systems.     

Cognitive learning efficiency through the use of design patterns in teaching

Nowadays we need to teach students how to become flexible problem solvers in a dynamic world. The pace in which technology changes and complexity increases requires increased efficiency in learning and understanding. This requires the engineers of tomorrow to quickly gain knowledge and insight outside their prime area of expertise. To transfer practical, how-to knowledge, to re-use design solutions and to teach students design solutions in the context of a specific domain, design patterns can be used. Design patterns offer a way to transfer knowledge that is more practical and ‘ready for use’ than a generic theory-based transfer of knowledge. However, the advantage of design patterns might go beyond re-use, design efficiency and flexibility. This paper argues that in addition to the benefits described above, there is a specific added value for the use of design patterns by students to acquire design skills and domain knowledge. To analyze this proposition we will analyze the literature on cognitive load and cognitive learning processes, and relate this to experiences from three case studies in which novices and experts were offered design patterns to develop and implement systems and processes. We will reflect on implications of the use of design patterns in computer-based teaching as well as on a potential support tool to improve the accessibility of pattern languages.     

How to guarantee compliance between workflows and product lifecycles?

Product lifecycle management (PLM) systems are widely used in the manufacturing industry. A core feature of such systems is to provide support for versioning of product data. As workflow functionality is increasingly used in PLM systems, the possibility emerges that the versioning transitions for product objects as encapsulated in process models do not comply with the valid version control policies mandated in the objects’ actual lifecycles. In this paper we propose a solution to tackle the (non-)compliance issues between processes and object version control policies. We formally define the notion of compliance between these two artifacts in product lifecycle management and then develop a compliance checking method which employs a well-established workflow analysis technique. This forms the basis of a tool which offers automated support to the proposed approach. By applying the approach to a collection of real-life specifications in a main PLM system, we demonstrate the practical applicability of our solution to the field.     

Generalized isotonic conditional random fields

Conditional random fields are one of the most popular structured prediction models. Nevertheless, the problem of incorporating domain knowledge into the model is poorly understood and remains an open issue. We explore a new approach for incorporating a particular form of domain knowledge through generalized isotonic constraints on the model parameters. The resulting approach has a clear probabilistic interpretation and efficient training procedures. We demonstrate the applicability of our framework with an experimental study on sentiment prediction and information extraction tasks.     

Verifying feature models using OWL

Feature models are widely used in domain engineering to capture common and variant features among systems in a particular domain. However, the lack of a formal semantics and reasoning support of feature models has hindered the development of this area. Industrial experiences also show that methods and tools that can support feature model analysis are badly appreciated. Such reasoning tool should be fully automated and efficient. At the same time, the reasoning tool should scale up well since it may need to handle hundreds or even thousands of features a that modern software systems may have. This paper presents an approach to modeling and verifying feature diagrams using Semantic Web OWL ontologies. We use OWL DL ontologies to precisely capture the inter-relationships among the features in a feature diagram. OWL reasoning engines such as FaCT++ are deployed to check for the inconsistencies of feature configurations fully automatically. Furthermore, a general OWL debugger has been developed to tackle the disadvantage of lacking debugging aids for the current OWL reasoner and to complement our verification approach. We also developed a CASE tool to facilitate visual development, interchange and reasoning of feature diagrams in the Semantic Web environment.     

Calling communities analysis and identification using machine learning techniques

The analysis of social communities related logs has recently received considerable attention for its importance in shedding light on social concerns by identifying different groups, and hence helps in resolving issues like predicting terrorist groups. In the customer analysis domain, identifying calling communities can be used for determining a particular customer’s value according to the general pattern behavior of the community that the customer belongs to; this helps the effective targeted marketing design, which is significantly important for increasing profitability. In telecommunication industry, machine learning techniques have been applied to the Call Detail Record (CDR) for predicting customer behavior such as churn prediction. In this paper, we pursue identifying the calling communities and demonstrate how cluster analysis can be used to effectively identify communities using information derived from the CDR data. We use the information extracted from the cluster analysis to identify customer calling patterns. Customers calling patterns are then given to a classification algorithm to generate a classifier model for predicting the calling communities of a customer. We apply different machine learning techniques to build classifier models and compare them in terms of classification accuracy and computational performance. The reported test results demonstrate the applicability and effectiveness of the proposed approach.     

A framework for regional association rule mining and scoping in spatial datasets

The motivation for regional association rule mining and scoping is driven by the facts that global statistics seldom provide useful insight and that most relationships in spatial datasets are geographically regional, rather than global. Furthermore, when using traditional association rule mining, regional patterns frequently fail to be discovered due to insufficient global confidence and/or support. In this paper, we systematically study this problem and address the unique challenges of regional association mining and scoping: (1) region discovery: how to identify interesting regions from which novel and useful regional association rules can be extracted; (2) regional association rule scoping: how to determine the scope of regional association rules. We investigate the duality between regional association rules and regions where the associations are valid: interesting regions are identified to seek novel regional patterns, and a regional pattern has a scope of a set of regions in which the pattern is valid. In particular, we present a reward-based region discovery framework that employs a divisive grid-based supervised clustering for region discovery. We evaluate our approach in a real-world case study to identify spatial risk patterns from arsenic in the Texas water supply. Our experimental results confirm and validate research results in the study of arsenic contamination, and our work leads to the discovery of novel findings to be further explored by domain scientists.     

WYSIWIB: exploiting fine‐grained program structure in a scriptable API‐usage protocol‐finding process

Bug‐finding tools rely on specifications of what is correct or incorrect code. As it is difficult for a tool developer or user to anticipate all possible specifications, strategies for inferring specifications have been proposed. These strategies obtain probable specifications by observing common characteristics of code or execution traces, typically focusing on sequences of function calls. To counter the observed high rate of false positives, heuristics have been proposed for ranking or pruning the results. These heuristics, however, can result in false negatives, especially for rarely used functions. In this paper, we propose an alternate approach to specification inference, in which the user guides the inference process using patterns of code that reflect the user's understanding of the conventions and design of the targeted software project. We focus on specifications describing the correct usage of API functions, which we refer to as API protocols. Our approach builds on the Coccinelle program matching and transformation tool, which allows a user to construct patterns that reflect the structure of the code to be matched. We evaluate our approach on the source code of the Linux kernel, which defines a very large number of API functions with varying properties. Linux is also critical software, implying that fixing even bugs involving rarely used protocols is essential. In our experiments, we use our approach to find over 3000 potential API protocols, with an estimated false positive rate of under 15% and use these protocols to find over 360 bugs in the use of API functions. Copyright © 2012 John Wiley & Sons, Ltd.     

SEIS++:一个油气勘探领域软件建造和集成的模式语言

工业化的软件复用从通用类库进化到了面向领域的应用框架和设计模式,与框架相比,设计模式更集中于软件体系结构中重复出现的设计韵律,它主要由可复用的抽象设计结构组成,特定领域内一组相关的设计模式构成了该领域的模式语言,它们可在领域内重复使用以完成某类特定系统的体系结构设计。     

Impact of working environments upon human-machine dialogues: a formal logic for the integrated specification of physical and cognitive ergonomic constraints on user interface design

A range of techniques have been developed to improve the integration of computer systems into complex working environments. For instance, computer aided design tools can be used to simulate operators' posture at a particular workstation. Fitting studies can then be used to validate potential layouts. Unfortunately, few of these techniques can also be used to support the development of interactive dialogues. This is a critical problem for systems where designers must distribute application data amongst a number of different presentation devices. The position of these displays can be used to reflect the salience and priority of information. This paper presents techniques that support both user interface development and workstation layout. First order logic can be used to represent and reason about constraints on the design of human computer dialogues. The same formalism can also be used to identify appropriate locations for presentation devices within their working context; control rooms and offices. The findings of ergonomic studies can then be applied to analyze the mental and physical demands imposed by the interactive dialogues that are supported by particular devices. Unfortunately, formal specifications provide little impression of what it would be like to interact with a system within a particular environment. We have developed simulation tools to address this problem. Prototype displays can be presented within three dimensional models of their working context. The resulting simulations are directly derived from formal specifications and can be shown to members of concurrent design teams. They also provide a medium for communication with potential operators.