D. Software
Refine
Year of publication
- 2016 (4) (remove)
Document Type
- Doctoral Thesis (4)
Language
- English (4)
Has Fulltext
- yes (4)
Keywords
- AUTOSAR (1)
- Affine Arithmetic (1)
- Combinatorial Testing (1)
- Gateway (1)
- Multi-Edge Graph (1)
- Software Testing (1)
- Software engineering (1)
- Transport Protocol (1)
- directed graphs (1)
- graph drawing algorithm (1)
Faculty / Organisational entity
Mixed-signal systems combine analog circuits with digital hardware and software systems. A particular challenge is the sensitivity of analog parts to even small deviations in parameters, or inputs. Parameters of circuits and systems such as process, voltage, and temperature are never accurate; we hence model them as uncertain values (‘uncertainties’). Uncertain parameters and inputs can modify the dynamic behavior and lead to properties of the system that are not in specified ranges. For verification of mixed- signal systems, the analysis of the impact of uncertainties on the dynamical behavior plays a central role.
Verification of mixed-signal systems is usually done by numerical simulation. A single numerical simulation run allows designers to verify single parameter values out of often ranges of uncertain values. Multi-run simulation techniques such as Monte Carlo Simulation, Corner Case simulation, and enhanced techniques such as Importance Sampling or Design-of-Experiments allow to verify ranges – at the cost of a high number of simulation runs, and with the risk of not finding potential errors. Formal and symbolic approaches are an interesting alternative. Such methods allow a comprehensive verification. However, formal methods do not scale well with heterogeneity and complexity. Also, formal methods do not support existing and established modeling languages. This fact complicates its integration in industrial design flows.
In previous work on verification of Mixed-Signal systems, Affine Arithmetic is used for symbolic simulation. This allows combining the high coverage of formal methods with the ease-of use and applicability of simulation. Affine Arithmetic computes the propagation of uncertainties through mostly linear analog circuits and DSP methods in an accurate way. However, Affine Arithmetic is currently only able to compute with contiguous regions, but does not permit the representation of and computation with discrete behavior, e.g. introduced by software. This is a serious limitation: in mixed-signal systems, uncertainties in the analog part are often compensated by embedded software; hence, verification of system properties must consider both analog circuits and embedded software.
The objective of this work is to provide an extension to Affine Arithmetic that allows symbolic computation also for digital hardware and software systems, and to demonstrate its applicability and scalability. Compared with related work and state of the art, this thesis provides the following achievements:
1. The thesis introduces extended Affine Arithmetic Forms (XAAF) for the representation of branch and merge operations.
2. The thesis describes arithmetic and relational operations on XAAF, and reduces over-approximation by using an LP solver.
3. The thesis shows and discusses ways to integrate this XAAF into existing modeling languages, in particular SystemC. This way, breaks in the design flow can be avoided.
The applicability and scalability of the approach is demonstrated by symbolic simulation of a Delta-Sigma Modulator and a PLL circuit of an IEEE 802.15.4 transceiver system.
A wide range of methods and techniques have been developed over the years to manage the increasing
complexity of automotive Electrical/Electronic systems. Standardization is an example
of such complexity managing techniques that aims to minimize the costs, avoid compatibility
problems and improve the efficiency of development processes.
A well-known and -practiced standard in automotive industry is AUTOSAR (Automotive
Open System Architecture). AUTOSAR is a common standard among OEMs (Original Equipment
Manufacturer), suppliers and other involved companies. It was developed originally with
the goal of simplifying the overall development and integration process of Electrical/Electronic
artifacts from different functional domains, such as hardware, software, and vehicle communication.
However, the AUTOSAR standard, in its current status, is not able to manage the problems
in some areas of the system development. Validation and optimization process of system configuration
handled in this thesis are examples of such areas, in which the AUTOSAR standard
offers so far no mature solutions.
Generally, systems developed on the basis of AUTOSAR must be configured in a way that all
defined requirements are met. In most cases, the number of configuration parameters and their
possible settings in AUTOSAR systems are large, especially if the developed system is complex
with modules from various knowledge domains. The verification process here can consume a
lot of resources to test all possible combinations of configuration settings, and ideally find the
optimal configuration variant, since the number of test cases can be very high. This problem is
referred to in literature as the combinatorial explosion problem.
Combinatorial testing is an active and promising area of functional testing that offers ideas
to solve the combinatorial explosion problem. Thereby, the focus is to cover the interaction
errors by selecting a sample of system input parameters or configuration settings for test case
generation. However, the industrial acceptance of combinatorial testing is still weak because of
the deficiency of real industrial examples.
This thesis is tempted to fill this gap between the industry and the academy in the area
of combinatorial testing to emphasizes the effectiveness of combinatorial testing in verifying
complex configurable systems.
The particular intention of the thesis is to provide a new applicable approach to combinatorial
testing to fight the combinatorial explosion problem emerged during the verification and
performance measurement of transport protocol parallel routing of an AUTOSAR gateway. The
proposed approach has been validated and evaluated by means of two real industrial examples
of AUTOSAR gateways with multiple communication buses and two different degrees of complexity
to illustrate its applicability.
Towards A Non-tracking Web
(2016)
Today, many publishers (e.g., websites, mobile application developers) commonly use third-party analytics services and social widgets. Unfortunately, this scheme allows these third parties to track individual users across the web, creating privacy concerns and leading to reactions to prevent tracking via blocking, legislation and standards. While improving user privacy, these efforts do not consider the functionality third-party tracking enables publishers to use: to obtain aggregate statistics about their users and increase their exposure to other users via online social networks. Simply preventing third-party tracking without replacing the functionality it provides cannot be a viable solution; leaving publishers without essential services will hurt the sustainability of the entire ecosystem.
In this thesis, we present alternative approaches to bridge this gap between privacy for users and functionality for publishers and other entities. We first propose a general and interaction-based third-party cookie policy that prevents third-party tracking via cookies, yet enables social networking features for users when wanted, and does not interfere with non-tracking services for analytics and advertisements. We then present a system that enables publishers to obtain rich web analytics information (e.g., user demographics, other sites visited) without tracking the users across the web. While this system requires no new organizational players and is practical to deploy, it necessitates the publishers to pre-define answer values for the queries, which may not be feasible for many analytics scenarios (e.g., search phrases used, free-text photo labels). Our second system complements the first system by enabling publishers to discover previously unknown string values to be used as potential answers in a privacy-preserving fashion and with low computation overhead for clients as well as servers. These systems suggest that it is possible to provide non-tracking services with (at least) the same functionality as today’s tracking services.
Typically software engineers implement their software according to the design of the software
structure. Relations between classes and interfaces such as method-call relations and inheritance
relations are essential parts of a software structure. Accordingly, analyzing several types of
relations will benefit the static analysis process of the software structure. The tasks of this
analysis include but not limited to: understanding of (legacy) software, checking guidelines,
improving product lines, finding structure, or re-engineering of existing software. Graphs with
multi-type edges are possible representation for these relations considering them as edges, while
nodes represent classes and interfaces of software. Then, this multiple type edges graph can
be mapped to visualizations. However, the visualizations should deal with the multiplicity of
relations types and scalability, and they should enable the software engineers to recognize visual
patterns at the same time.
To advance the usage of visualizations for analyzing the static structure of software systems,
I tracked difierent development phases of the interactive multi-matrix visualization (IMMV)
showing an extended user study at the end. Visual structures were determined and classified
systematically using IMMV compared to PNLV in the extended user study as four categories:
High degree, Within-package edges, Cross-package edges, No edges. In addition to these structures
that were found in these handy tools, other structures that look interesting for software
engineers such as cycles and hierarchical structures need additional visualizations to display
them and to investigate them. Therefore, an extended approach for graph layout was presented
that improves the quality of the decomposition and the drawing of directed graphs
according to their topology based on rigorous definitions. The extension involves describing
and analyzing the algorithms for decomposition and drawing in detail giving polynomial time
complexity and space complexity. Finally, I handled visualizing graphs with multi-type edges
using small-multiples, where each tile is dedicated to one edge-type utilizing the topological
graph layout to highlight non-trivial cycles, trees, and DAGs for showing and analyzing the
static structure of software. Finally, I applied this approach to four software systems to show
its usefulness.