Acer Computer (Shanghai) Limited
3F, No. 168 Xizang medium road, Huangpu District, Shanghai, China
Declaration of Conformity
We, Acer Computer (Shanghai) Limited
3F, No. 168 Xizang medium road, Huangpu District, Shanghai, China Contact Person: Mr. Easy Lai Tel: 886-2-8691-3089 Fax: 886-2-8691-3000 E-mail: easy_lai@acer.com.tw

Hereby declare that:

Product: Trade Name: Model Number:
37 LCD TV Monitor Acer AT3705
Is compliant with the essential requirements and other relevant provisions of the following EC directives, and that all the necessary steps have been taken and are in force to assure that production units of the same product will continue comply with the requirements.
EMC Directive 89/336/EEC as attested by conformity with the following harmonized standards:
-. EN55022:1998 + A1:2000 + A2:2003, AS/NZS CISPR22:2002, Class B -. EN55024:1998 + A1:2001 + A2:2003 -. EN55013:2001 + A1:2003 -. EN55020:2002 + A1:2003 -. EN61000-3-2:2000, Class D -. EN61000-3-3:1995 + A1:2001
Low Voltage Directive 73/23/EEC as attested by conformity with the following harmonized standard:

-. EN60065:2001

RoHS Directive 2002/95/EC on the Restriction of the Use of certain Hazardous Substances in Electrical and Electronic Equipment
--------------------------------
Easy Lai / Director Acer Computer (Shanghai) Limited

Combining Model-Based Testing and Machine Learning

Roland GROZ

LIG, Universit de Grenoble, France

TAROT Summer School 2009

Acknowledgments

Muzammil Shahbaz

Keqin Li (now with SAP Research) Alexandre Petrenko (CRIM, Canada)
Doron Peled (seminal paper BBC), David Lee, Khaled El Fakih

Outline

MBT and software engineering trends Machine Learning for test automata Integration: MBT and ML, integration testing Experiments and case studies Research directions
Traditional software cycle
Specification - Validation Customer

Vendor Implementation

Assembling fully controlled components
MBT in software development

Acceptance tests

System tests Integration tests

Design

Unit tests Implementation
Challenge: CBSE with 3rd party
Assemblingill controlled components
Component Based Software Engineering
High Level System Design Components Components selection & selection Integration

Requirement Analysis

Integrated System
Rapid Development Reuse Components Reduce cost Flexibility Ease of integration

Issues

Interactions Behaviors Validation
Understanding the System of Black Box Components is a challenge
How do I perform system behavioral analysis? How do I identify integration problems ?

Soft. Engineering trends

MDE & MBT

Growing

trend in some industries (e.g. embedded) Derive design, code and tests (MBT) Models = 1st class citizens

Dominant

growing trend Absence of (formal) models Pb maintaining spec <-> model
MDE & MBT in the reverse

MDE assumption

Start
from model, formal spec Models = 1st class citizens
Test Driven Development (XP, Agile)

Tests

are spec: 1st class citizens Formal models ? No way !

Proposed approach

Derive
models from tests, & combine with MBT Reconcile Test-Driven (or code-driven) dvt with Models

Technical Goals

Reverse Engineering
Understanding the behaviors of the black box components
by deriving the formal models of the components/system Can also serve documentation purposes (tests for doc)

System Validation

Being able to derive new systematic tests Analyzing the system for anomalies / compositional problems
by developing a framework for integration testing of the system of black box components

Approach

observes

Learner

learn s

Tester

(Validation Techniques)
Model(s) (Finite State Machine)

es deriv

What do we achieve?
Models (to understand the system more "formally") System is validated for anomalies
Reverse engineer Model Requirements Component generate Scenario 1 Scenario 2 Sollicitations
Partial, incremental and approximate characterization

Objections

Answers
Model is derived from bugged components

Derived

tests will consider bug=feature
Incremental: stopping criterion ?

Machine learning

Various types of Machine Learning
Artificial Intelligence (& datamining)

Ability

to infer rules, recognize patterns Learning from samples E.g. neural networks

Two major techniques

Statistical
(bayesian) inference from collection of data -> e.g. Weka tool in testing Grammatical inference of language from theoretical computer science
Learning languages from samples
Finding a minimum DFA (Deterministic Finite Automaton) is NP-HARD
Complexity of automaton identification from given data. [E. Gold 78]
Even a DFA with no. of states polynomially larger than the no. of states of the minimum is NPComplete
The minimum consistent DFA problem cannot be approximated within any polynomial. [Pitt & Warmuth 93]

Probably Approximately Correct (PAC)
A theory of the learnable. [L.G. Valiant 84]

e eL ssiv Pa

in g a rn

Background Work

Passive Learning
"Learning from given positive/negative samples" NP-Complete

Active Learning

"Learning from Queries" (Regular Inference) Angluin's Algorithm L* [Angluin 87]
Learns Deterministic Finite Automaton (DFA) in polynomial time Black Box Checking [Peled 99] Learning and Testing Telecom Systems [Steffen 03] Protocol Testing [Shu & Lee 08]

Dana Angluin

Yale University

Applied in

Concept of the Regular Inference

(Angluin's Algorithm L*)

Input Alphabet
ip * rs h e mb from m e es ri ue q

The Algorithm L*

ct eje /r
eq uiv (D alen FA c co e qu nje e ctu ries r e)

Black Box Machine

pt cce a
co " y un es te " o re xa r m p le
Oracle Final Minimum DFA Conjecture
Assumptions: The input alphabet is known Machine can be reset
Complexity : O( | | m n ) | | : the size of the input alphabet n : the number of states in the actual machine 19 m : the length of the longest counterexample

Our Context of Inference

Test Strategies and heuristics
Components having I/O behaviors I/O are structurally complex (parameters) ip * rsh sets Formidable size be input of m

m f ro me ies r ue q

Learned Models can be used to eq uiv generate tests to find (D que alen FA c discrepancies r c ies e

on jec t ur e)

System of Communicating Black Box Components

pt ce ac

t jec / re
Oracle Final DFA Conjecture
Enhanced State Machine Models Mealy Machines Parameterized Machines More adequate for complex systems DFAs may result in transition blow up

Preliminaries

Mealy Machine: M = (Q, I, O, , , q0)
Q : set of states I : set of input symbols O : set of output symbols : transition function : output function q0 : initial state

Input Enabled

dom() = dom() = Q I
Q = {q0, q1, q2, q3} I = {a,b} O = {x,y}
Mealy Machine Inference Algorithm

The Algorithm LM*

Input set I
t I* t pu r om ou s f rie ue q

gs t ri n s

eq uiv (M qu alen ea ly c eries ce on jec t ur e)

Black Box Mealy Machine

ut utp o
co " y un es te " o re xa r m ple
Oracle Final Mealy Conjecture
Assumptions: The input set I is known Machine can be reset For each input, the corresponding output is observable
Basic principles of Angluins algorithm (mod.)

Discriminating sequences

a b x x x x x

I={a, b}

Build queries row.col submit row.col -> record output <for col
S (span seq) for States SI transitions

a b aa ab

x y x y x

Conjecture

tr1: a/x

tr2: b/x

tr4: b/x

tr3: a/y

Black Box Mealy Machine Component
Observation Table is an empty string
Mealy Machine Inference Algorithm LM* (1/5)

a b x x x

Observation Table (SM,EM,TM)
Concepts: Closed Consistency
Output Queries: se, s (SM SM I), e EM

= a/ x

is an empty string
Mealy Machine Inference Algorithm LM* (2/5)

Concept: Closed

SM SM SM I
Concepts: Closed : All the rows in SM I must be equivalent to the rows in SM
Same behaviour = known state

Consistency

Mealy Machine Inference Algorithm LM* (3/5)

Making Conjecture tr

tr2 EM

b x x x x x

tr4 I={a, b}

SM SM I

Counterexample: ababbaa component's response: x x x x x x y conjecture's response:M,EM,TM) x x x Observation Table (S x x x x

tr4: b/x tr3: a/y

Mealy Machine Inference Algorithm LM* (4/5)
Processing Counterexamples E
b x x x x x a ab aba abab ababb ababba ababbaa aa b abb abaa ababa ababbb
a x y x x x x x y y x x x y x
b x x x x x x x x x x x x x x
Counterexample: a b a b b a a Method:
Add all the prefixes of the counterexample to SM
Mealy Machine Inference Algorithm LM* (5/5)

Concept: Consistency

a a x y x x x x x y y x x x y x b x x x x x x x x x x x x x x xy yy xx xx xy xx xy yy yy xx xx xy yy xy
a ab aba abab ababb ababba ababbaa aa b abb abaa ababa ababbb
Concepts: Closed Consistency : All the successor rows of the equivalent rows must also be equivalent
Consistency check can be avoided If all rows in SM are inequivalent The rows in SM become equivalent due to the method of processing counterexamples in the table
New Method for Processing Counterexamples (The Algorithm LM+)

Counterexample

ab abbaa Add all the suffixes to EM
All rows remain inequivalent (inconsistency never occurs)

a a b aa ab x y x y x

aa xy yy xx xx yy

baa xxx xxx xxy xxx xxx

bbaa abbaa xxxy xxxx xxxx xxxy xxxx xxxxx yxxxx xxxxy xxxxx yxxxx
Observation Table (SM,EM,TM) before processing counterexample

Observation Table (SM,EM,TM) after processing counterexample
Comparison of the two Methods
Total Output Queries in LM+ : 64 Total Output Queries in LM* : 86
Final Observation Table (SM,EM,TM) after processing counterexample according to LM+
Final Observation Table (SM,EM,TM) after processing counterexample according to LM*
Total Output Queries in LM+ : 64
Complexity of LTotal Output Queries in LM* : 86 M*:
O( |I| n m + |I| m n) Complexity of LM+: O( |I| n + |I| m n) I : the size of the input set n : the number of states in the actual machine Observation Table (SM,EM,TM) Observation Table (SM,EM,TM) m : the length of the longest counterexample
after processing counterexample according to LM+
after processing counterexample according to LM*
Experiments with Edinburgh Concurrency Workbench
Examples Size of Input set

No. of States

No. of No. of Output Output Queries for Queries for LM* LM+ 1404 3094

Reduction Factor

R ABP-Lossy Peterson2 Small VM Buff3 Shed2 ABP-Safe TMR1 VMnew CSPROT
0 1,22 1,43 0,18 1,13 1,24 0,04 2,1 -0,19 0,86 0,67
0 R Small Peterson2 ABP-Lossy VM Buff3 Shed2 TMR1 VMnew CSPROT ABP-Safe Examples Output Queries 2000 4000

System Architecture

System of communicating Mealy Machine Components Components are deterministic and input-enabled System has External and Internal i/o interfaces
External interface is controllable External and Internal interfaces are observable
Single Message in Transit and Slow Environment
Learning & Testing Framework
Step 2(a): Compose Models Step 3: Refine Models Step 1: Learn Models Product Step 2(b): Analyze Product [compositional problem] Learned Models No Compositional Problems Product Step 4: Generate Tests from Product Discrepancy trace Step 5: Resolve Discrepancy (exception, crash, out of memory,.?) [error found] [discrepancy as counterexample ] [problem as counterexample]
Step 2(c): Confirm Problem on System [problem confirmed] Terminate

[no discrepancy]

Contributions

Mealy Machine Inference

Improvements in the basic adaptation from the Angluin's algorithm

Parameterized Machine Inference Framework of Learning and Testing of integrated systems of black box Mealy Machine components Tool & Case Studies (provided by Orange Labs)

The tool RALT

(Rich Automata Learning and Testing)

Case Studies

1. 2. 3.
Concurrency Workbench Air Gourmet Nokia 6131, N93, Sony Ericsson W300i

Real Systems

Experimented with Media Player
Domotics (Orange Labs' Smart Home Project)
Devices: Dimmable Light, TV, Multimedia Systems)

Air Gourmet

Goal: Learning & Testing the System

Mealy Machines

Components Passenger Check-in Flight Reservation Meals Manager
Size of No. of States No. of Errors Input Set 4
Error Types NPE, IIE, Date Parsing Exception NPE, IIE, IAE
NPE: Null Pointer Exception, IIE: Invalid Input Exception, IAE: Illegal Input Exception

Nokia 6131

Goal: Learning the behaviors of the Media Player
Music P1.wav Music P2.wav

{ Play, Pause, Stop }

Nokia 6131 / N93 / Sony Ericsson W300i
p1.start(p1.wav) / p1.STARTED p1.stop() / p1.stopped p1.start(p1.wav) / p1.STARTED
D 1.CLOSE lose() / p p1.c
p2.start(p2.wav) / Exp q3

Nokia 6131 (PFSM)

p2.start(p2.wav) / p2.STARTED p2.stop() / p2.STOPPED

p2.close / p2.CLOSED

p2.start(p2.wav) / p2.STARTED
p1.start(p1.wav) / Exp Nokia 93 / Sony Ericsson W300i (PFSM)
p1.start(p1.wav) / p1.STARTED p2.start(p2.wav) / p2.STARTED p1.stop() / p1.STOPPED p2.stop() / p2.STOPPED
p1.start(p1.wav) / p1.STARTED p2.start(p2.wav) / p2.STARTED
p1.close() / p1.CLOSED p2.close() / p2.CLOSED

Domotics

Goal: Learning the interactions of the devices
Acer AT3705-MGW ProSyst Dimmable Light Philips Streamium400i
Device Light (ProSyst) Media Renderer (Philips) Domotics (Interaction Model)

Size of Input Set 9

No. of States 16

Time (minutes) 30

Conclusion
Reverse Engineering Enhanced State Models
Improved Mealy machine inference Parameterized Machine Inference
Framework for Learning & Testing of Integrated Systems of Black Box Mealy machines The tool RALT that implements the reverse engineering and integration testing framework Experiments with real systems in the context of Orange Labs.

Perspectives

Work in Progress

Approach

for detecting sporadic errors Learning Nondeterministic Automata

Future Work

Generation for Model Refinements Framework for PFSM models

Behind the Curtain

DoCoMo: A Motivational Example in Orange Labs
uploads score on the Docomo's server

(Web Connection)

Hidden Behavior:

(Game)

User's scores are uploaded to the server through web

Hidden Interaction:

The Game component interacts with the Web component for connection

Mealy Machine Quotients

Let be a set of strings from I then
the states s1 and s2 are -equivalent if they produce same outputs for all the strings in A quotient based upon -equivalence is called -quotient
= {a, b, ab, ba, bb, bba}
q0 and q2 are -Equivalent q1 and q3 are -Equivalent

Mealy Machine M

-quotient of M
Relation between the Conjecture and the Black Box Machine

EM-Quotient

Conjecture from the Observation Table (SM,EM,TM)
Closed (and Consistent) Observation Table (SM,EM,TM) Black Box Mealy Machine
Parameterized Finite State Machine (PFSM)
PFSM Algorithm LP* (a view)
a b (1,s ) (6,t 6) (1,s ) (6, t 36) (1,s ) (6, t 36) (1,s ) (6, t 6) (1,s ) (6, t 36) (1,s ) (6, t 36) (1,s ) (6, t 6) Black Box PFSM Component

I = {a,b}, DI = N {}

a b 1 b 6 aa ab 1 ab 6
(,s ) (,s ) (,s ) (,s ) (,s ) (,s ) (,s )

u(x 1)/s

Observation Table (SP,R,EP,TP)

tr1: a/s

tr2: b({1})/s

tr3: b({6})/t({6})

tr6: b({6})/t({36})

tr4: a/s tr5: b({1})/s