ILTAM logo English
Send to Print Close Window

 
 
SwSTE07

Doctoral Symposium
Presentations by Ph.D. Students

October the 30th

In the Doctoral Symposium track, students will report on their work in progress.  We expect that this will yield interaction with peers, academicians, and industry people thereby contributing to the student as well as to the community.

Chaired by: Dr. Michael Rodeh, IBM Research Lab in Haifa

Morning Session

Title

Author

Institute
A Methodology and Infrastructure for a Unified Product and Project Lifecycle Management Framework
 Sharon Amira and Valeria Perelman
 Technion – Israel Institute of Technology
Using LSCs for Scenario Authoring in Tactical Simulators
 Yoram Atir and
David Harel
 Weizmann Institute
Nonlinear Bipartite Matching
 Yael Berstein
 Technion – Israel Institute of Technology
Towards Trace Visualization and Exploration for Reactive System
 Shahar Maoz
 Weizmann Institute
Retroactive Abstraction in Java with Whiteoak
 Itay Maman
 Technion - Israel Institute of Technology/Computer Science

Afternoon session


 An improved Algorithm for the Black-and-White Coloring Problem on Trees Shira Zucker Ben-Gurion University of the Negev
Refactoring to Statecharts Guy Wiener
Dr. Mayer Goldberg
 Ben-Gurion University of the Negev
JTL - The Java Tools Language Itay Maman Technion - Israel Institute of Technology/Computer Science
Optimization of DNIDS Deployment Strategy Rami Puzis Ben-Gurion University of the Negev
Evolving machine Chess players with GP
 Ami Hauptman Ben-Gurion University of the Negev

Papers Abstracts

Morning Session

A Methodology and Infrastructure for a Unified Product and Project Lifecycle Management Framework-
Amira Sharon, Valeria Perelman, and Dov Dori, Technion - Israel Institute of Technology
Developing and sustaining complex products and systems requires collaboration of multidisciplinary teams, coordination of resources and utilization of adequate tools within enterprises. This constellation can be considered system-of systems or a grand system that comprises three intertwined subsystems: the enterprise, the project and the product. Despite the obvious links between these subsystems, each uses its distinct ontology and toolset. This conceptual separation hinders effective handling of lifecycle activities of the project and the product within the enterprise. To demonstrate the relations between these three subsystems, consider the testing activities focused on verifying the performance of individual software and hardware components, through large subassemblies to the entire operational software-intensive system. What needs to be developed, tested, and delivered is determined by the product definition that is documented in functional and non-functional product or system requirements developed by multidisciplinary teams. When each component should and can be developed and tested is stated in the project plan. The plan is dynamically re-estimated, re-evaluated, and re-planned depending on different parameters like project progress compared with the plan, availability of recourses, risks, and technological developments or breakthroughs that impact the value of the product under development. Whether carrying out the development mission is feasible is determined by the developing enterprise, its size, structure, management criteria, other projects running in parallel, commitments, and many other aspects.
BACK

Using LSCs for Scenario Authoring in Tactical Simulators
Yoram Atir and David Harel, Weizmann Institute.
Computer simulators and the so-called serious games are referred to as “tactical” when their main focus is on decision making, rather than on technical skills. In order to make high level functionalities in the applications susceptible to assessment and control, the simulations in these systems are carried out by actors assigning intentions to semi-autonomous agents. The intentions are typically related to other entities, and so the simulation is to a large extent defined by high level interactions between entities. Thus inter-entity scenarios are at the heart of tactical simulations. They are set up in order to practice and assess the interactions of actors with respect to some local doctrine.
The doctrine and the scenarios that embody it are often expressed in a modal, temporal way. For example, “If X occurs, action Y must be initiated within Z seconds”. Inter-entity scenarios are typically defined by Subject Matter Experts (SMEs), and may be used in simulator design and testing, as well as in simulation runs. The former relates to the expected behavior of (semi)autonomous agents and the latter to the expected behavior of human trainees.
Two challenges in this area are the creation of believable agent behavior and the orchestration of different agents and behaviors into credible, controlled scenarios. A major issue is the gap between the partial and informal specifications given by SMEs in the design stages of the system and the implementation of the behavior, which requires the utilization of formal methods by computer experts. In a larger context, that of the general domain of reactive systems, a similar gap was one of the main forces that triggered the introduction of the language of live sequence charts (LSCs), and the subsequent work on the play-in/play-out methodology and the supporting Play-Engine tool.
The play-in technique involves a user-friendly and natural way to play in scenario-based behavior directly from the system’s GUI (or some abstract version thereof, such as an object-model diagram), during which LSCs are generated automatically. The play-out technique makes it possible to play out the behavior; that is, to execute the system as constrained by the grand sum of the scenario based information. These ideas are supported in full by the Play-Engine.
In the present work, we show how to adapt the LSC language and the play-in/play-out techniques, so that they can be applied beneficially to real-time tactical simulation. Among other things, this makes it possible for end-users and SMEs to naturally and intuitively specify LSCs for use in scenario orchestration and behavior monitoring.
BACK

Nonlinear Bipartite Matching
Yael Berstein and Shmuel Onn, Faculty of Industrial Engineering and Management, Technion – Israel Institute of Technology
We consider a generalization of the standard linear bipartite matching problem defined as follows. For each edge in a complete bipartite graph there is a given d-dimensional weight vector. A functional on d-dimensional space is also given. The weight of a matching is the sum of the weight vectors of all edges in the corresponding matching. The objective value of a matching is the value of the functional on its weight vector. The problem is to find a perfect matching achieving maximal or minimal objective value. This problem is generally intractable: even for standard 1-dimensional weights, minimizing a family of very simple convex univariate functions is NPhard. Using the projection of the Birkhoff polytope of bistochastic matrices by the given weights, we develop several efficient algorithms for solving the nonlinear bipartite matching problem, including a deterministic algorithm for maximizing convex objectives, a randomized algorithm for optimizing arbitrary objectives, and approximative algorithms for norm optimization. In particular, for binary weights, our results imply a polynomial-time algorithm for maximizing convex objectives and a polynomial-time randomized algorithm for optimizing arbitrary objectives.
BACK

Towards Trace Visualization and Exploration for Reactive Systems
Shahar Maoz, Asaf Kleinbort and David Harel, Weizmann Institute.
We present a rich and highly dynamic technique for the visualization and exploration of the execution traces of reactive systems. The input is a designer's inter-object scenario-based behavioral model, given as a set of UML2-compliant live sequence charts (LSC), and a scenario-based execution trace of the system. Our method allows one to visualize, and navigate through, the activation and  progress of the scenarios given in the charts as they "come to life" during execution. Thus, we tie the visualization of system execution traces with model-driven design.  Among other things, we support both event-based and real-time-based tracing, and use details-on-demand mechanisms, multi-scaling grids, and gradient coloring methods.   We have implemented and tested our ideas in a prototype tool called the Tracer.
BACK

Retroactive Abstraction in Java with Whiteoak
Itay Maman, Dr. Yossi Gil, Technion - Israel Institute of Technology/Computer Science
Java is nominally typed---a type (i.e., a class or an interface) is compatible with another if it is declared, directly or indirectly as such, by means of keyword extends or implements.This paper discusses the design and implementation of Whiteoak, a Java extension that introduces structural type equivalence and subtyping into the language: In a nutshell, a struct A in Whiteoak is similar to an interface of Java except that a class, interface, or another struct B is compatible with A if the repertoire of public function and data members of B is a superset of that of A. After arguing that structural subtyping addresses common software design problems, and promotes the development of loosely coupled modules without compromising type safety, we describe language design issues, including subtyping in face of self-referencing struct's, dealing with static members, compile-time operators for computing the ``meet'' and ``join'' of structs, and the fascinating mechanism which allows members renaming in the process of subtyping. Interesting is also Whiteoak support of type classes, which are structural types where a default, overridable, behavior is specified for some of the methods. We also describe how Whiteoak was implemented without changes to the underlying JVM, and how this implementation met the challenge of maintaining the identity of the this variable in type classes.
BACK

Afternoon Session:

An improved Algorithm for the Black-and-White Coloring Problem on Trees
Shira Zucker, Daniel Berend, Ephraim Korach, Ben-Gurion University of the Negev
The Black-and-White Coloring (BWC) problem is defined as follows. Given an undirected graph G and positive integers B,W, determine whether there exists a partial coloring of G such that B vertices are colored in black and W vertices in white (with all other vertices left uncolored), such that no black vertex and white vertex are adjacent. The BWC problem has been introduced and proved to be NP-complete by Hansen et al. [1]. In the same paper, an O(n3) algorithm for trees was given. We improve their algorithm and reduce its running time to O(n2 log3 n).
BACK

Refactoring to Statecharts
Guy Wiener, Dr. Mayer Goldberg, Ben-Gurion University of the Negev
This work offers a methodology for refactoring objectoriented code into statecharts. Currently, most statecharts tools generate code from specifications, and migrating an entire application requires a complete redesign. Refactoring to statecharts allows for gradual migration, making statecharts more practical for existing applications. The statechart model is a formal model for asynchronous activities in a reactive system. The original approach to using statecharts is based on automatic tools that generates skeletal code from a statechart specification. This approach requires specifying the statecharts before writing any code. A specificationdriven approach is unsuitable for use within existing projects that do not employ statecharts, and for incremental conversion of an existing system to using statecharts. This work proposes that the statechart formal model will be deducted incrementally from existing code. Such incremental approach enhances the execution model and adds to it semantic information. Our approach is to use an additional thread for the Statecharts engine, that will run concurrently with preexisting threads. Hence, until such a time when the entire application is managed by the Statecharts engine, the application uses at least two threads. Initially, the application threads preform all the operations, and the statechart thread is empty. The next steps in the refactoring consists of moving responsibilities for handling events from the application threads to the statecharts thread. When the entire application is converted to use the statecharts execution model, the engine running within the statechart thread will manage all the events.
Converting code into a statechart is done in two steps: First, methods are converted into activities, in a similar way to the Moving Methods to Method Objects refactoring. Activities are an asynchronous version of the Command design pattern. Second, these activities are added to the statechart. The statechart engine manages activities by actions such as start, stop, pause and resume. Because activities are asynchronous, there are no constraints on the duration of an activity. Specifically, it does not have to be completed within a single step of the statechart. The advantage of activities, as opposed to methods or parts of methods, is that activities are firstclass objects, and can be stored, recalled, managed and moved among threads. The activities of a statechart are managed by actions. Actions can be attached either to a transition or to a state property, such as onEntry or onExit. Therefore, to move an activity A from an application thread to the statechart thread, the programmer should add actions for managing A to a state or a transition in the statechart. In this work, we describe refactoring heuristics for adding activities to a statechart and for splitting large activities into smaller ones. Splitting a large activity to smaller activities enables to finetune the execution of the smaller activities, and can help in making the application more responsive. Using a statechart to model activities makes complex asynchronous behaviors more manageable and easier to maintain. A statechart describes how an application handles a sequence of events by starting and stopping activities, sequentially or in parallel, more concisely then regular code. Thus, an incremental conversion of an application to use a statechart helps to maintain an application with complex eventhandling without requiring a complete rewrite.
BACK

JTL - The Java Tools Language
Itay Maman, Dr. Yossi Gil, Technion, Israel Institute of Technology/Computer Science
JTL, (the Java Tools Langauge, pronounced ``Gee-tel'') is a universal and high-level query langauge for selecting program elements. It is designed to serve the development of source code software tools for Java, and for programming langauge extensions. Applications include definition of joinpoints for aspect-oriented programming, fixing type constraints for generic programming, specification of encapsulation policies, definition of micro-patterns, etc. We argue that the JTL expression of each of these is systematic, concise, intuitive and general.
JTL relies on a simply-typed relational database for program representation, rather than an abstract syntax tree. The underlying semantics of the language is that of queries formulated in First Order Predicate Logic augmented with transitive closure (FOPL*). Special effort was taken to ensure terse, yet very readable expression of logical conditions. The JTL pattern public abstract class, for example, matches all abstract classes which are publicly accessible, while class { public clone(); } matches all classes in which method clone() is public. To this end, JTL relies on a Datalog-like syntax and semantics, enriched with quantifiers and pattern matching which all but entirely eliminate the need for recursive calls.
BACK

Optimization of DNIDS Deployment Strategy
Rami Puzis, Ben-Gurion University of the Negev
Malicious code such as viruses, computer worms, Spyware, and Trojans account for more than 10% of the total traffic of Network Service Providers (NSP). Recent studies suggest that only 44% of the users connected to the Internet are protected by updated anti-virus software. One way to prevent users from being infected by malicious code is to clean the traffic at the NSP level. The NSP traffic can be monitored and cleaned by Distributed Network Intrusion Detection Systems (DNIDS) that may be deployed on the NSP routers/links. It is not realistic to inspect the traffic of all the routers/links of the NSP. Theoretic models suggest protecting the most significant routers/links in order to slow down propagation of the malicious code in the entire network. In this study we choose which routers/links to protect based on Group Betweenness Centrality (GBC) that can be used as a measure of their collaborative influence on the communication in the NSP infrastructure. In this study we develop a framework aimed at slowing down or even preventing the propagation of malicious code. Preliminary results of the first part of the framework include development of an efficient algorithm for computation of GBC. 1 The main advantage of this algorithm is that its running time does not depend on the size of the network but only on the size of the evaluated group. We have used this algorithm as part of a process that finds the group of nodes with maximal GBC 2. The process itself is based on heuristic search in which the contribution of individual nodes to the GBC of the partial group is used to guide the search. Finally we learned that the near to optimal group can be found using a greedy algorithm whose GBC is negligibly close to the GBC of the optimal group. Preliminary results of the second part of the framework include the development of a simulation tool34 that supports: Generating NSP network topology including core routers, edge routers, access routers, and hosts; Simulating propagation of malicious code (a.k.a. Viruses and Worms); Simulating DNIDS that is deployed on some of the NSP routers/links; Assisting in locating the optimal deployment of DNIDS based on the algorithms developed in the first part of the framework; and presenting statistical information such as the number of infected hosts.
BACK

Evolving machine Chess players with GP
Ami Hauptman, Ben Gurion University of the Negev
Genetic Programming (GP) is a sub-class of evolutionary algorithms, in which a population of solutions to a given problem, embodied as LISP expressions, is improved over time by applying the principles of Darwinian evolution. At each stage, or generation, each solution’s quality is measured and assigned a numerical value, called fitness. During the course of evolution, natural (or, in our case, artificial) selection takes place, wherein individuals with high fitness values are more likely to generate offspring. In the course of my research, I applied GP to evolve strategies for Chess endgames. My first set of experiments gave rise to GP individuals capable of drawing (or even winning) against CRAFTY—a world-class chess program. Some of the success of this methodology may be related to the inspiration gained from examining work on how humans play Chess. Next, I applied this notion further, and developed a novel method of integrating search with knowledge into GP-individuals. Current results have shown that the number of nodes CRAFTY examines while solving the mate-in-N for N = 4 and N = 5 may be significantly reduced with evolved search. This result awarded me and my thesis advisor, Prof. Moshe Sipper, a silver medal and a monetary reward at prestigious international competition for developing human competitive programs. I am currently focusing on the broader aspects of developing patterns of knowledge, using neural networks and statistical methods, as well as cognitive ones.
BACK
Send to Print Close Window