Improving the performance of OCL constraint solving with novel heuristics for logical operations: a search-based approach

A common practice to specify constraints on the Unified Modeling Language (UML) models is using the Object Constraint Language (OCL). Such constraints serve various purposes, ranging from simply providing precise meaning to the models to supporting complex verification and validation activities. In many applications, these constraints have to be solved to obtain values satisfying the constraints, for example, in the case of model-based testing (MBT) to generate test data for the purpose of generating executable test cases. In our previous work, we proposed novel heuristics for various OCL constructs to efficiently solve them using search algorithms. These heuristics are enhanced in this paper to further improve the performance of OCL constraint solving. We performed an empirical evaluation comprising of three case studies using three search algorithms: Alternating Variable Method (AVM), (1?+?1) Evolutionary Algorithm (EA), and a Genetic Algorithm (GA) and in addition Random Search (RS) was used as a comparison baseline. In the first case study, we evaluated each heuristics using carefully designed artificial problems. In the second case study, we evaluated the heuristics on various constraints of Cisco’s Video Conferencing Systems defined to support MBT. Finally, the third case study is about EU-Rent Car Rental specification and is obtained from the literature. The results of the empirical evaluation showed that (1?+?1) EA and AVM with the improved heuristics significantly outperform the rest of the algorithms.     

Empirically evaluating OCL and Java for specifying constraints on UML models

The Object Constraint Language (OCL) has been applied, along with UML models, for various purposes such as supporting model-based testing, code generation, and automated consistency checking of UML models. However, a lot of challenges have been raised in the literature regarding its applicability in industry such as extensive training, slow learning curve, and significant effort to use OCL due to lack of familiarity of practitioners. To confirm these challenges, empirical evidence is needed, which is severely lacking in the literature. To build such preliminary evidence, we report a controlled experiment that was designed to evaluate OCL by comparing it with Java; a programming language that has also been used to specify constraints on UML models. Results show that the participants using OCL perform as good as the participants working with Java in terms of three objective quality metrics (i.e., completeness, conformance and redundancy) and two subjective metrics (i.e., applicability and confidence level). In addition, the participants using OCL performed consistently well for all the constraints of varying complexity, while fluctuating results were obtained for the participants using Java for the same constraints. Based on the empirical evidence, we can conclude that it does not make much difference to use OCL or Java for specifying constraints on UML models. However, the participants working with OCL performed consistently well on specifying constraints of varying complexity suggesting that OCL can be used to model complicated constraints (commonly observed in industrial applications) with the same quality as for simpler constraints. Moreover, additional analyses on the constraints when using Java and OCL tools revealed that tools are needed to specify fully correct constraints that can be used to support automation.     

Specification of temporal properties with OCL

The Object Constraint Language (OCL) is widely used to express static constraints on models and object-oriented systems. However, the notion of dynamic constraints, controlling the system behavior over time, has not been natively supported. Such dynamic constraints are necessary to handle temporal and real-time properties of systems.In this paper, we first add a temporal layer to the OCL language, based syntactically on Dwyer et al.'s specification patterns. We enrich it with formal scenario-based semantics and integrate it into the current Eclipse OCL plug-in. Second, we translate, with a compositional approach, OCL temporal properties into finite-state automata and we connect our framework to automatic test generators. This way, we create a bridge linking model driven engineering and usual formal methods.     

Extending symbolic execution for automated testing of stored procedures

Stored procedures in database management systems are often used to implement complex business logic. Correctness of these procedures is critical for flawless working of the system. However, testing them remains difficult due to many possible database states and constraints on data. This leads to mostly manual testing. Newer tools offer automated execution for unit testing of stored procedures but the test cases are still written manually. We propose an approach of using dynamic symbolic execution for generating automated test cases and corresponding database states for stored procedures. We model the constraints on data imposed by the schema and the SQL statements, treating values in database tables as symbolic. We use SMT solver to find values that will drive the stored procedure on a particular execution path. We instrument the internal execution plans generated by PostgreSQL to extract constraints. We use Z3 to generate test cases consisting of table data and procedure inputs. Our evaluation using stored procedures from a large business application and various GitHub repositories quantifies the evidence of effectiveness of our technique by generating test cases that lead to schema constraint violations and user-defined exceptions.     

Refactoring OCL annotated UML class diagrams

Refactoring of UML class diagrams is an emerging research topic and heavily inspired by refactoring of program code written in object-oriented implementation languages. Current class diagram refactoring techniques concentrate on the diagrammatic part but neglect OCL constraints that might become syntactically incorrect by changing the underlying class diagram. This paper formalizes the most important refactoring rules for class diagrams and classifies them with respect to their impact on attached OCL constraints. For refactoring rules that have an impact on OCL constraints, we formalize the necessary changes of the attached constraints. Our refactoring rules are specified in a graph-grammar inspired formalism. They have been implemented as QVT transformation rules. We finally discuss for our refactoring rules the problem of syntax preservation and show, by using the KeY-system, how this can be resolved.     

Using genetic algorithms to generate test sequences for complex timed systems

The generation of test data for state-based specifications is a computationally expensive process. This problem is magnified if we consider that time constraints have to be taken into account to govern the transitions of the studied system. The main goal of this paper is to introduce a complete methodology, supported by tools, that addresses this issue by representing the test data generation problem as an optimization problem. We use heuristics to generate test cases. In order to assess the suitability of our approach we consider two different case studies: a communication protocol and the scientific application BIPS3D. We give details concerning how the test case generation problem can be presented as a search problem and automated. Genetic algorithms (GAs) and random search are used to generate test data and evaluate the approach. GAs outperform random search and seem to scale well as the problem size increases. It is worth to mention that we use a very simple fitness function that can be easily adapted to be used with other evolutionary search techniques.     

在带OCL约束的状态图下测试线索的自动生成*

保证软件质量的前提下如何减少测试用例规模是测试设计的关键技术之一。提出一种带OCL约束的状态图测试线索的自动生成方法。该方法自动解析类图和带OCL约束的状态图的XML模型文件,获取相应的状态节点邻接表,再结合状态对-事件约束集合生成带OCL约束的测试线索。实例研究表明,通过OCL约束冲突判断可避免不可行测试线索的生成,减少测试用例数目,达到降低测试成本的目的。实验结果证明了该方法的可行性和有效性。     

An agent-oriented approach to change propagation in software maintenance

Software maintenance and evolution is a lengthy and expensive phase in the life cycle of a software system. In this paper we focus on the change propagation problem: given a primary change that is made in order to meet a new or changed requirement, what additional, secondary, changes are needed? We propose a novel, agent-oriented, approach that works by repairing violations of desired consistency rules in a design model. Such consistency constraints are specified using the Object Constraint Language (OCL) and the Unified Modelling Language (UML) metamodel, which form the key inputs to our change propagation framework. The underlying change propagation mechanism of our framework is based on the well-known Belief-Desire-Intention (BDI) agent architecture. Our approach represents change options for repairing inconsistencies using event-triggered plans, as is done in BDI agent platforms. This naturally reflects the cascading nature of change propagation, where each change (primary or secondary) can require further changes to be made. We also propose a new method for generating repair plans from OCL consistency constraints. Furthermore, a given inconsistency will typically have a number of repair plans that could be used to restore consistency, and we propose a mechanism for semi-automatically selecting between alternative repair plans. This mechanism, which is based on a notion of cost, takes into account cascades (where fixing the violation of a constraint breaks another constraint), and synergies between constraints (where fixing the violation of a constraint also fixes another violated constraint). Finally, we report on an evaluation of the approach, covering effectiveness, efficiency and scalability.     

Using UML and OCL to maintain the consistency of spatial data in environmental information systems

The Object Constraint Language (OCL) is a subset of the well-known Unified Modeling Language (UML) that allows specifying constraints over entities representing concepts from the application domain. The purpose of this paper is to describe a specific extension of OCL to model spatial constraints of Environmental Information Systems (EIS). These new features are applied to the agricultural spreading of organic matter. In this context, it is important to model a set of spatial constraints that define precisely where spreading can take place. For example, organic matters can never be spread inside certain natural areas. At present, some tools allow producing integrity checking mechanisms in different languages (Java, C#, SQL, etc.) from specifications of non-spatial constraints expressed in OCL. For instance, the SQL code generated by OCL2SQL can be used to check if a database verifies constraints or to forbid inserting data that do not verify them. In order to check spatial constraints in EIS, we implemented the “Spatial OCL” proposed in this paper into an extension of OCL2SQL.     

Perturbation-based user-input-validation testing of web applications

User-input-validation (UIV) is the first barricade that protects web applications from application-level attacks. Most UIV test tools cannot detect semantics-related vulnerabilities in validators, such as filling a five-digit number to a field that accepts a year. To address this issue, we propose a new approach to generate test inputs for UIV based on the analysis of client-side information. In particular, we use input-field information to generate valid inputs, and then perturb valid inputs to generate invalid test inputs. We conducted an empirical study to evaluate our approach. The empirical result shows that, in comparison to existing vulnerability scanners, our approach is more effective than existing vulnerability scanners in finding semantics-related vulnerabilities of UIV for web applications.     

Improving the definition of general constraints in UML

An important aspect in the specification of conceptual schemas is the definition of general constraints that cannot be expressed by the predefined constructs provided by conceptual modeling languages. This is generally achieved by using general-purpose languages like OCL. In this paper we propose a new approach that facilitates the definition of such general constraints in UML. More precisely, we define a profile that extends the set of predefined UML constraints by adding certain types of constraints that are commonly used in conceptual schemas. We also show how our proposal facilitates reasoning about the constraints and their automatic code generation, study the application of our ideas to the specification of two real-life applications, and present a prototype tool implementation.

A methodology for engineering collaborative and ad-hoc mobile applications using SyD middleware

Today’s web applications are more collaborative and utilize standard and ubiquitous Internet protocols. We have earlier developed System on Mobile Devices (SyD) middleware to rapidly develop and deploy collaborative applications over heterogeneous and possibly mobile devices hosting web objects. In this paper, we present the software engineering methodology for developing SyD-enabled web applications and illustrate it through a case study on two representative applications: (i) a calendar of meeting application, which is a collaborative application and (ii) a travel application which is an ad-hoc collaborative application. SyD-enabled web objects allow us to create a collaborative application rapidly with limited coding effort. In this case study, the modular software architecture allowed us to hide the inherent heterogeneity among devices, data stores, and networks by presenting a uniform and persistent object view of mobile objects interacting through XML/SOAP requests and responses. The performance results we obtained show that the application scales well as we increase the group size and adapts well within the constraints of mobile devices.     

Converting heterogeneous statistical tables on the web to searchable databases

Much of the world’s quantitative data reside in scattered web tables. For a meaningful role in Big Data analytics, the facts reported in these tables must be brought into a uniform framework. Based on a formalization of header-indexed tables, we proffer an algorithmic solution to end-to-end table processing for a large class of human-readable tables. The proposed algorithms transform header-indexed tables to a category table format that maps easily to a variety of industry-standard data stores for query processing. The algorithms segment table regions based on the unique indexing of the data region by header paths, classify table cells, and factor header category structures of two-dimensional as well as the less common multidimensional tables. Experimental evaluations substantiate the algorithmic approach to processing heterogeneous tables. As demonstrable results, the algorithms generate queryable relational database tables and semantic-web triple stores. Application of our algorithms to 400 web tables randomly selected from diverse sources shows that the algorithmic solution automates end-to-end table processing.     

Prediction of Web Page Accesses by Proxy Server Log

As the population of web users grows, the variety of user behaviors on accessing information also grows, which has a great impact on the network utilization. Recently, many efforts have been made to analyze user behaviors on the WWW. In this paper, we represent user behaviors by sequences of consecutive web page accesses, derived from the access log of a proxy server. Moreover, the frequent sequences are discovered and organized as an index. Based on the index, we propose a scheme for predicting user requests and a proxy-based framework for prefetching web pages. We perform experiments on real data. The results show that our approach makes the predictions with a high degree of accuracy with little overhead. In the experiments, the best hit ratio of the prediction achieves 75.69%, while the longest time to make a prediction only requires 2.3 ms.     

Formal object-oriented development of a voting system test oracle

We report on the formal development of a test oracle for an electronic-voting system, detailing our approach which was based on a lightweight integration of Event-B, UML, and Java. This lightweight integration focuses on a coherent development process rather than on formal integration at the model/language level. We then briefly review alternative development approaches involving the use of JML and OCL. We conclude that the use of the OCL would offer few benefits, if any, in our formal development process.     

基于CPN模型的REST服务架构标准特征验证方法研究

当前REST服务架构广泛应用于大规模、可扩展的分布式Web系统中,若应用REST服务架构时不遵循其标准特征,则可能导致基于REST服务架构的Web系统出现性能下降、可扩展性低等问题。因此,实现基于REST服务架构的Web系统前,需要对该系统设计是否满足REST服务架构标准特征进行验证,以提升基于REST服务架构的Web系统的研发质量。提出一种基于CPN模型的REST服务架构标准特征验证方法,即对REST服务架构的五个标准特征约束进行CPN建模,并使用模型状态空间执行路径同步匹配的验证方法,以应用系统的CPN模型和标准特征约束的CPN模型为基础,对模型状态空间中的各自执行路径进行同步匹配,若路径可同步执行完毕,则说明该应用系统满足该REST标准特征约束。以基于REST服务架构的课程管理Web系统为例,验证上述方法的可用性和有效性。实验结果表明,本文所提验证方法可以有效确认基于REST服务架构的Web应用系统设计是否符合REST服务架构的标准特征约束,并在不符合标准特征约束时提供直观、可行的执行数据,便于后续完成应用系统设计缺陷定位及修正。     

Applications of web mining for marketing of online bookstores

The purpose of this study is to identify potential customers of online bookstores through web content mining without customers’ transaction records and demographic information. Our study first creates a list of scholars whose research field is in information technology and categories of IT expertise. We then use a search engine to count the numbers of web pages related to scholars and expertise. These data are pre-processed with three key steps before being used: filtering abnormal data, normalizing data, and generating binary data. Association analysis and hierarchical cluster analysis are employed to generate the clusters of scholars and the clusters of expertise. In order to test the accuracy of using web mining to predict clients’ interested booklists, our study evaluates the accuracy of prediction through survey. The results show that the accuracy rate of the recommended booklists targeted on potential customers (scholars) is statistically significant.     

Towards Intelligent Semantic Caching for Web Sources

An intelligent semantic caching scheme suitable for web sources is presented. Since web sources typically have weaker querying capabilities than conventional databases, existing semantic caching schemes cannot be directly applied. Our proposal takes care of the difference between the query capabilities of an end user system and web sources. In addition, an analysis on the match types between a user's input query and cached queries is presented. Based on this analysis, we present an algorithm that finds the best matched query under different circumstances. Furthermore, a method to use semantic knowledge, acquired from the data, to avoid unnecessary access to web sources by transforming the cache miss to the cache hit is presented. To verify the effectiveness of the proposed semantic caching scheme, we first show how to generate synthetic queries exhibiting different levels of semantic localities. Then, using the test sets, we show that the proposed query matching technique is an efficient and effective way for semantic caching in web databases.     

Secure multi-group data hiding based on gemd map

Numerous data hiding schemes have been recently proposed based on section-wise strategy. The purpose of these approaches is to enhance security by using a unique key to generate a table. But these approaches are not matched between the embedding secret data length for binary bits and the length of the notation system in the section-wise strategy. In order to enhance the security of secret data and increase embedding capacity, we will propose a secure multi-group data hiding scheme based on General Exploiting Modification Direction (GEMD) map in this paper. Three major advantages exist in our scheme. First is flexibility for the number and combination of elements. Second is the removal of spatial redundancy in our method while maintaining embedding capacity above 1 bpp. Lastly, this method avoids the overflow/underflow problem. Experimental results show that our method enhances embedding capacity and maintains good visual stego image quality. In terms of security, the proposed scheme is more secure than LSB replacement method in terms of resisting visual attack and RS testing.     

Modeling and validating Mondex scenarios described in UML and OCL with USE

This paper describes the Mondex case study with UML class diagrams and restricting OCL constraints. The constraints have been formulated either as OCL class invariants or as OCL pre- and postconditions. The proposed two models include UML class diagrams and OCL constraints which have been checked by the UML and OCL tool USE (UML-based Specification Environment). USE allows validation of a model by testing it with scenarios. The Mondex case study has been validated by positive and negative test cases. The test cases allow the validity of the various constraints to be traced and checked. Validation results are presented as textual protocols or as UML sequence diagrams where starting, intermediate, and resulting system states are represented by UML object diagrams. UML sequence diagrams, UML object diagrams, and textual protocols are shown with varying degrees of detail for the attributes, constraints, and executed commands. J. C. P. Woodcock