Transcript traces - Virtual building 8

1
Following the traces of
OADymPPac …
Pierre Deransart
CR INRIA-Paris-Rocquencourt
The OADymPPaC project (Tools for Dynamic Analysis and Debugging of
Constraint Programs), whose COSYTEC was a partner, officially ended in 2004.
One of the objective was generic trace definition. Focused by short delays on tracer
prototypes realisation and trace analysis, the project did not go deep in the problem
of trace creation and management. We invite you here to follow the path initiated
Chip User's Club, Paris
16/10/2008
1
by OADymPPaC,
until
some epistemological ultimate consequences.
2
Key figures
A workforce of 3,700
Jan. 2007
2,900 scientists
1,000 doctoral candidates
450 post-docs
300 R&D engineers
8 Research
Centres (2008)
1,500 budgetary positions
570 research scientists
740 ETA
300 interns
Budget: 162 M€ (tax not incl.)
including 20% from contracts, software licenses, etc.
Chip User's Club, Paris 16/10/2008
2
3
INRIA Lille
Nord Europe
Location
Metz
Lannion
INRIA Paris
Rocquencourt
INRIA Rennes
Bretagne Atlantique
Nantes
INRIA Nancy
Grand Est
INRIA
Besançon
Saclay
Île-de-France
Lyon
Headquarters
Strasbourg
INRIA Grenoble
Rhône-Alpes
INRIA Bordeaux
Sud-Ouest
Research Centre
External research
project-team
Chip User's Club, Paris 16/10/2008
Montpellier
Marseille
INRIA Sophia Antipolis
Méditerranée
Pau
3
The Research Centres
Lille - Nord Europe
Rennes - Bretagne Atlantique
Nancy - Grand Est
Paris - Rocquencourt
Grenoble - Rhône-Alpes
Saclay - Île-de-France
Bordeaux - Sud-Ouest
Chip User's Club, Paris 16/10/2008
Sophia Antipolis - Méditerranée
4
4
5
Try to remember….
1999
« Sur la route de Rocquencourt » par Pissaro …
2004
Chip User's Club, Paris 16/10/2008
2004, so long time ago….
5
6
Chip User's Club, Paris 16/10/2008
6
CONTEXT, HISTORY
7
From DiSCiPl to OADymPPaC
•DiSCiPl (1997-2000): to improve debogage of constraint solvers: resulted in
prototypes which remained « ad-hoc » ones for correctness and performance
analysis. This project has shown the usefulness of semi-automated approaches
based on trace analysis by visualization tools.
Book: P. Deransart and M. Hermenegildo and J. Maluszynski, Analysis and
Visualization Tools for Constraint Programming, LNCS 1870, 2000
•OADymPPaC (2001-2004) URL: http://contraintes.inria.fr/OADymPPaC
participants: A. Aggoun, T. Baudel, P. Deransart, M. Ducassé, F.Fages, J.D.
Fekete, N. Jussien, C. de Sainte-Marie, …
Challenges :
•
Interoperability of the tools : complete separation between trace production
and trace analysis, studied and realized by different specialists
•
scaling: possibilité possibility to consider thausends of variables and constraints
using specialized HMI
The project resulted in prototypes et products, but limited to the constraint
resolution domain. Several problems have been identified.
Chip User's Club, Paris 16/10/2008
7
PROBLEMS
8
Can such approach be extended to other domains?
1.Trace interpretation: to give a meaning to a trace, reconstruction models
(trace analysis, interpretative semantics IS).
2.Sémantics of the traces of a given family of processes (trace generation
model, observational semantics OS).
3.Data stream managment between the observed and observing processes:
trace filtering, tracer driver, workload balance, interactions, properties of the
stream (efficiency, invariance of the semantics, faithfulness)
Relationships with other research and application domains: eventcondition-action models, data stream analysis, cognitive sciences
Chip User's Club, Paris 16/10/2008
8
The two traces of a process
(Full Traces)
•Virtual Trace TV = <S0,et*>
•Actual Trace
9
SO
TA = <S0,wt*>
SI
Notion of FAITHFULNESS:
TV
E
E: extraction
I
TA
Chip User's Club, Paris 16/10/2008
I: interpretation
(reconstruction)
E
°
I = I
9
°
E = i
Small example (extract of Prolog trace)
10
chrono nu(u) lp(u) port
pd(u)
1
1
1
Call
goal
S2
goal:-p(X),eq(X,b).
2
2
2
Call
p(X)
S3
p(a).
3
2
2
Exit
p(a)
S4
p(b).
4
3
2
Call
eq(a,b)
S5
eq(X,X).
5
3
2
Fail
eq(a,b)
S6
6
2
2
Redo p(a)
S7
7
2
2
Exit
p(b)
S8
8
4
2
Call
eq(b,b)
S9
9
4
2
Exit
eq(b,b)
S10
10
1
1
Exit
goal
S11
Chip User's Club, Paris 16/10/2008
10
Reached
virtual state
But if the trace is smaller …?
11
nu(u) port
1
Call
2
Call
2
Exit
3
Call
3
Fail
2
Redo
2
Exit
4
Call
4
Exit
1
Chip User's Club, Paris 16/10/2008
What can we see ?
Exit
11
12
Chip User's Club, Paris 16/10/2008
12
13
PLAN:
domains and “challenges”
1. Tracer development for dynamic analysis of programs
2. Modelling and abstraction
3. Data mining et data stream filtering, ECA models and WEB
semantics
4. Analysis of human behaviour
5. Brain, memory prothesis
6. Epistemology
Idea: traces are everywhere,
investigating on traces, is investigating on ideas too
Chip User's Club, Paris 16/10/2008
13
Everywhere ?
14
Gérard
Berry
2007
http://www.college-de-france.fr/default/EN/all/ger_ber/index.htm
Chip User's Club, Paris 16/10/2008
14
1- Tracer Construction for dynamic analysis of
programs
1. Incremental development of tracer (full trace)
2. Trace filtering and query (language for trace events
selection), Tracer Driver
3. Interactions (server tracer / clients analysers)
4. Optimization of the communication (with faithfulness)
5. MDA Approach «trace componants» (enrichment, fusion,
abstraction, selection)
6. Genericity
Chip User's Club, Paris 16/10/2008
15
15
C4RBCP
16
TV
TRslamV
TchromeV
TCHRV
Chip User's Club, Paris 16/10/2008
16
And
querying
17
Grand Challenge 1: conception et manipulation of
traces (« traces algebra»)
Enrichment
Selection
Fusion
Abstraction
Genericity
Chip User's Club, Paris 16/10/2008
17
18
2-Modelling and abstraction
Full Trace
Intricated abstractions levels
Chip User's Club, Paris 16/10/2008
18
19
Modelling and abstraction (genericity)
Chip User's Club, Paris 16/10/2008
19
Grand Challenge 2: models of trace production (SO)
Abstract interpretation give a possible theoretical
framework for the OS
possible use of « Fluent calculus »
Tracer implementation, simulations and verifications
are possible for a domain of processes (« model
checking », Clarke, Emerson, Sifakis, Turing 2007)
Theoretical trace Analysis (relationships with trace theory,
The Book of Traces, 1995),
Chip User's Club, Paris 16/10/2008
20
20
3-Data mining and interogation of data stream,
semantic WEB, ECA Models
ADSL traffic
Looking for a meaning…
Chip User's Club, Paris 16/10/2008
21
21
22
Data mining as trace analysis
Using data stream analysis algorithms in order to recognize objects
(optimized traces)
•Selection of suspicious portions of programs (Zaidman & al, 2005)
•« model checking » for intrusion detection (Garavel & al. 2004) on
execution traces
•Symmetries discovery
(OADymPPaC)
Chip User's Club, Paris 16/10/2008
22
23
Data stream analysis with unknown origin
Massive flow analysis (probabilistic algorithms, Rabin 1980)
Query langages of data flows (Arasu, 2002)
Interactions between observer/observed and between
traces (ECA models and WEB semantics, Alferes et al.
2004)
Chip User's Club, Paris 16/10/2008
23
24
Grand Challenge 3: to interpret traces (IS)
Using data stream analysis algorithms to recognize objects
in the trace (identification of observables)
Trace query language : efficient filtering
To trace knowledge use and management
Chip User's Club, Paris 16/10/2008
24
25
4-Human behaviour Analysis
Go around the limits af automation
To trust the data
Formalisation of contexts (data fusion), traces of
contexts and human behaviour
Construction of scenarios from traces
Till were can we or shall we go?
Chip User's Club, Paris 16/10/2008
25
26
Trusting data (access to the knowledge)
Knowledge base = rule system = computations
Using it require more than just computations: seeking, identifying, reasoning
(without predefined strategy)
Example: problem internet sites guarantees (ex law of 13 août 2004 on “ la
certification des sites internet dédiés à la santé” (Haute Autorité à la Santé))
HON code (Health On the Net): ex
•Qualification of writers
•Justification of affirmations
•Clear distinction between edited contents and advertisement
•Transparency of founding
•Personal data protection, keeping traces on consultations or updates
•…
Chip User's Club, Paris 16/10/2008
26
Construction od a virtual world (Lyon1/INRETS)
Virtual Trace
TRACES
Actual Trace
Chip User's Club, Paris 16/10/2008
27
27
An “Infernal” Example
28
Le Monde de l'Intellligence, num 11 janv-fev-mars 08 Sudoku infernal p 60 (par Bernard Gervais)
Chip User's Club, Paris 16/10/2008
28
29
Chip User's Club, Paris 16/10/2008
29
30
Experimentation
To build and compare traces of the player’s behaviour and of the
automaton
•D’analyser le comportement du joueur
•D’identifier la règle utilisée par le joueur
•De mesurer la satisfaction du joueur
•De comparer avec la résolution automatique
•D’identifier les points de réelle difficulté du joueur
•De corréler de la difficulté pour le joueur et la difficulté théorique
Chip User's Club, Paris 16/10/2008
30
31
Grand Challenge 4:
Analyze of a knowledge domain
Construction of scenarios
Limits of the formalization (beginning of the “human” work)
The ability to build “good” traces
Is mandatory in order to perform “good” analysis
Chip User's Club, Paris 16/10/2008
31
32
5-Brain: a world of fusions
Chip User's Club, Paris 16/10/2008
32
33
Actual Trace Twt = <(S0,)wt*>
Unbounded sequence of trace events wt
wt : (t, At)
•t : chrono: time of the trace
•At: set of
attributes values
Chip User's Club, Paris 16/10/2008
33
34
La mémoire
Personal Memory Project: Memex (Vannevar Bush, 1945)
Accumulation of trace events (multimedia)
------------------------------Mechanisms of the human memory:
Axes (Chapoutier, 2006):
•Sensations
•Temporal (work, episodic / reference, sustainable)
•Abstract (procedural memory and implicit memory )
each memory has its recall mode (implicit, inconscient / explicit, conscient)
Chip User's Club, Paris 16/10/2008
34
35
Gand Challenge 5: personal memory artefact
Axes: digitalization/numerisation (sensorial), remanent and support
(temporal line), conscient recall(abstract)
Towards a memory protese?
•“base of stances” (Kiss, Quinqueton 2004)
•Mechanisms for deduction and for recell (LISFS, logical information
system, Padiolo, Sogonneau, Ridoux 2004)
•mechanisms for data organization (ontology's) et to forget
Personal memory organization system
Chip User's Club, Paris 16/10/2008
35
6- Epistemology as theory of knowledges
36
Discretization-spatialisation/numerisation/manipulation
Big steps:
•20 centuries after beginning of néolitic: first numerations (astro)
•12th century BC alphabetic system (“grammatization”)
•The printing allows the writing to invade society
•17th century, the machine tool is the reproduction of discretized
gesture
•1834 discretization sounds and images
•Economy of immaterial (management of knowledges)
Information processing plays a dominant role in all spheres of activity
(industry or research) and is based on an uninterrupted accumulation
of traces ….
Chip User's Club, Paris 16/10/2008
36
37
Grand Challenge 6:
society viewed as a system of interacting traces
http://www.inria.fr/40ans/forum/video.fr.php
Le réseau numérique, à l'origine d'un nouveau modèle
industriel Conférence de Bernard Stiegler
Les nouvelles technologies : révolution culturelle et cognitive
Conférence de Michel Serres
etc…
Chip User's Club, Paris 16/10/2008
37
38
Following the traces of ….
Jusqu’où ne risque-t-on pas d’aller trop loin?
L’homme réinventé?
Chip User's Club, Paris 16/10/2008
Thank you!
38