Combinatorial search problems are ubiquitous in many fields of Computer Science. A common technique for addressing them is the exploitation of lower bounds: optimistic estimates of the cost for transforming a state into a solution. But how to compute such estimates? The proposed BARQ project addresses this question, in a highly inter-disciplinary fashion encompassing Classical Planning, Probabilistic Planning, Scheduling, and Model Checking. To our knowledge, BARQ is the first project addressing all these areas in unison. We use abstraction to obtain the lower bounds, and we use abstraction refinement to incrementally improve these bounds. Combined with upper bounding methods, this yields highly practical anytime algorithms that guarantee bounds on the quality of the current solution. The core technique we focus on is state abstraction, which imposes an equivalence relation over states. We consider a recent scheme, nested state aggregation (NSA), for constructing such abstractions. NSA incorporates a computational trick allowing fine-tuned design of the equivalence relation by selecting individual pairs of states to aggregate into one. It has been shown in Classical Planning that, in theory, this approach dominates most other known abstraction schemes. That power hinges, however, on perfect selection of the states to aggregate. Hardly anything is known about how to make this selection. BARQ fills this gap. To this end, we draw on research traditions from Probabilistic Planning and Model Checking, concerned with state abstraction and abstraction refinement. These traditions have addressed similar questions, but for very different purposes forcing the abstraction to preserve the exact set of solutions. Our research relaxes this restriction to obtain lower bounding methods instead, thus uncovering several new connections between the addressed areas. BARQ is mainly motivated by basic research questions. However, each of the four areas addressed has a tradition of practical applications, which we will leverage for the final evaluation of the developed techniques.

Either in defense or civil domains, the awareness about security issues of information or communication systems is increasing. The vulnerabilities or malicious attacks can have dramatic results. The security of information or communication systems should be achieved at several levels: • Processes and organizations to establish the security based on risk analysis and to define security policy; • Physical infrastructure, securing their access or their sealing; • Software components provide security features on all layers of the information system. The OSEP project addresses clearly the third point (in software). The OSEP project will provide innovative technology for testing the correct implementation of the properties expected for safety. A recent study by the Software Engineering Institute (SEI) of Carnegie Mellon University (cf http://www.sei.cmu.edu/tsp/research/) has shown on a representative sample of information systems that 90% of security incidents were caused by attacks on software fault. A key challenge for a good management of the security policy resides in the ability to identify reliable security features, and to ensure their proper implementation. The security policy is implemented through security components, such as cryptographic components, smart cards, authentication components, firewalls or filtering devices. These security features are present in a multitude of systems for both civil and defense fields. The strategic objective of OSEP project aims to strengthen security through innovative techniques. These techniques use test generation driven by models for testing features and safety components. The expected results will lead to both a management of off-line test generation from schemas for security properties and complementary techniques for in-line generation and test execution. These technologies are based on complex research issues, both in terms of test coverage associated with the security properties, in test generation algorithmic and in the management of the generation and execution for online testing. The level of technological maturity of the research project, classified on the scale of the TRL (Technology Readiness Level) is at level 2 and 3 for the part concerning the safety test online from templates, at level 3 and 4 for the test generation part driven by the security properties from schemas. The OSEP project is a research project that combines an innovative SME, Smartesting technology, specialist in tests generation from model and an INRIA team, the project team CASSIS - Combining Approaches For the Security of Infinite State Systems - specializing in the field of verification and security. The search results will be tested in two contexts: security components and software radio, in partnership with the Department “Analyse et Développement de Logiciels de Sécurité” of DGA Maîtrise de l’information.