Background @ Michelin

• 100+ applications running in production
• Not (fully) covered by tests
• Documentation most likely outdated
• MUST be maintained for ~20 years!

The only way to ensure stability while fixing a bugis to learn how the application behaves.

A first classic solution to express these behaviours is to model them, e.g. with Input Output Symbolic Transition Systems.

But writing such models is an heavy task and error prone.

Not suitable for Michelin applications.

Hence the need for a model inference approach.

If models don't exist (or are toocomplicated to write), let's build them!

Model Inference

Inference is the act or process of reaching a conclusionabout something from known facts or evidence.

A (human) domain expert can deduce the meaning of an application execution by reading its traces.

What about doing the same, programmatically?

An expert system is a computer system thatemulates the decision-making ability of a human expert.

Model Inference Framework

Model Generator Layers

Hypotheses On The Rules

• A rule can only be applied a limited number of times on the same knowledge base
• The inference rules are Modus Ponens (soundness)
• Facts are Horn clauses

Modus Ponens + Horn clauses completeness

Layer 1: Trace Filtering

HTTP requests and responses related to assets(CSS files, JavaScript files, images) are meaningless.

Structured HTTP Traces

Let  t = req1, resp1, ..., reqn, respn   be a raw HTTP trace composed of an alternate sequence of HTTP request reqi and HTTP response respi. The structured HTTP trace σ of t is the sequence (a1(p), θ1)...(an(p), θn) where:

• ai is the HTTP verb used to perform the request in reqi,
• p is the parameter set {URI, request, response},
• θi is a valuation p → Dp which assigns a value to each variables of p. θ is deduced from the values extracted from reqi and respi.

The resulting trace set derived from raw traces is denoted ST.

Example

GET("https://github.com/", req0, resp0)
GET("https://github.com/login", ...)
POST("https://github.com/session", ...)
GET("https://github.com/", ...)
GET("https://github.com/willdurand", ...)
GET("https://github.com/willdurand/Geocoder", ...)
POST("https://github.com/logout", ...)
GET("https://github.com/", ...)

Layer 2: IOSTS Transformation

The model is not extrapolated:

traces(δ1) = ST

Example

Layers 3-N: IOSTS Abstraction

Composed of rules that emulate the ability of a human expertto simplify transitions, to analyze transition syntax in orderto deduce more meaningful information related to thetargeted application, and to construct more abstract models.

Each layer takes an IOSTS given by the direct lower one. It represents the current base of facts.

Layer 3

Layer 3 contains low level, generic rules thatcan be reused against different applications.

rule "Identify Login Page"
when
    $t: Transition(
        Action == GET,
        Guard.response.content contains('login-form')
    )
then
    modify ($t) { Assign.add("isLoginPage := true") }
end

Layer 3 - Example

Layer 4

Layer 4 allows to infer a more abstract modelcomposed of more expressive actions.

rule "Identify Authentication"
when
    $t1: Transition(Action == GET, Assign contains "isLoginPage:= true",
                    $t1final := Lfinal)
    $t2: Transition(Action == PostRedirection, Linit == $t1lfinal,
                    $t2linit := Linit)
    not  Transition(Linit == $t2linit)
then
    insert(new Transition("Authentication",
        Guard($t1.Guard,$t2.Guard), Assign($t1.Assign, $t2.Assign),
        $t1.Linit, $t2.Lfinal
    ))
    retract($t1)
    retract($t2)
end

Layer 4 - Example

Need More?

Conclusion

Cons

• Writing (and maintaining) rules is harder than expected
• Preserving traces(M) = ST leads to rather large models

Pros

• Original approach to derive IOSTS models
• It Works™

Current Status

Working on an implementation for Michelin's industrial systems.