20198569605

Committed 13 Dec 2025 10:10PM UTC coverage: 94.914% (+0.4%) from 94.471%

Build # 20198569605

Build Type

Pull #153

github

Committed by

web-flow

Commit Message

Merge 6a71fc929 into 879958926

Pull Request Pull Request #153: Implementation for learning MMLTs, new model for collecting statistics

Run Details

1823 of 1873 new or added lines in 77 files covered. (97.33%)

1 existing line in 1 file now uncovered.

14258 of 15022 relevant lines covered (94.91%)

1.73 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.75

/filters/cache/src/main/java/de/learnlib/filter/cache/mmlt/MMLTCacheConsistencyTest.java

/* Copyright (C) 2013-2025 TU Dortmund University
 * This file is part of LearnLib <https://learnlib.de>.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package de.learnlib.filter.cache.mmlt;

import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Objects;
import java.util.Set;

import de.learnlib.oracle.EquivalenceOracle.MMLTEquivalenceOracle;
import de.learnlib.query.DefaultQuery;
import de.learnlib.time.MMLTModelParams;
import net.automatalib.automaton.mmlt.MMLT;
import net.automatalib.symbol.time.InputSymbol;
import net.automatalib.symbol.time.TimeStepSequence;
import net.automatalib.symbol.time.TimedInput;
import net.automatalib.symbol.time.TimedOutput;
import net.automatalib.symbol.time.TimeoutSymbol;
import net.automatalib.word.Word;
import net.automatalib.word.WordBuilder;
import org.checkerframework.checker.nullness.qual.Nullable;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Searches for counterexamples by comparing the behavior of the hypothesis and the query cache. If there are multiple
 * counterexamples, the shortest one is returned.
 *
 * @param <I>
 *         input symbol type (of non-delaying inputs)
 * @param <O>
 *         output symbol type
 */
@SuppressWarnings("PMD.TestClassWithoutTestCases") // not a traditional test class
public class MMLTCacheConsistencyTest<I, O> implements MMLTEquivalenceOracle<I, O> {

    private static final Logger LOGGER = LoggerFactory.getLogger(MMLTCacheConsistencyTest.class);

    private final TimedSULTreeCache<I, O> sulCache;
    private final MMLTModelParams<O> modelParams;

    MMLTCacheConsistencyTest(TimedSULTreeCache<I, O> sulCache, MMLTModelParams<O> modelParams) {
        this.sulCache = sulCache;
        this.modelParams = modelParams;
    }

    private DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> queryCache(Word<TimedInput<I>> word) {
        WordBuilder<TimedInput<I>> wbInput = new WordBuilder<>(word.length());
        WordBuilder<TimedOutput<O>> wbOutput = new WordBuilder<>(word.length());

        this.sulCache.pre();
        for (TimedInput<I> sym : word) {
            if (sym instanceof InputSymbol<I> ndi) {
                TimedOutput<O> res = this.sulCache.step(ndi);
                wbInput.append(ndi);
                wbOutput.append(res);
            } else if (sym instanceof TimeStepSequence<I> ws) {
                TimedOutput<O> res = this.sulCache.timeoutStep(ws.timeSteps());
                wbInput.append(ws);

                if (res == null) {
                    wbOutput.append(new TimedOutput<>(this.modelParams.silentOutput()));
                } else {
                    wbOutput.append(res);
                }
            } else {
                throw new IllegalArgumentException("Symbol type " + sym.getClass() + " must not be used in cache.");
            }
        }
        this.sulCache.post();

        return new DefaultQuery<>(wbInput.toWord(), wbOutput.toWord());
    }

    /**
     * The cache does not use timeout symbols. Using these instead of time-step-sequences has several performance
     * benefits. This function converts a query with a time-step-sequence to one that uses timeout symbols where
     * possible.
     *
     * @param originalQuery
     *         the original query
     *
     * @return the converted query
     */
    private DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> convertTimeSequences(DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> originalQuery) {
        WordBuilder<TimedInput<I>> wbInput = new WordBuilder<>();
        WordBuilder<TimedOutput<O>> wbOutput = new WordBuilder<>();

        int symIdx = 0;
        Word<TimedInput<I>> queryInput = originalQuery.getInput();
        Word<TimedOutput<O>> queryOutput = originalQuery.getOutput();

        while (symIdx < queryInput.length()) {
            TimedInput<I> inputSym = queryInput.getSymbol(symIdx);
            TimedOutput<O> outputSym = queryOutput.getSymbol(symIdx);
            symIdx++;

            if (inputSym instanceof InputSymbol<I> ds) {
                wbInput.append(ds);
                wbOutput.append(outputSym);
            } else if (inputSym instanceof TimeStepSequence<I> ws) {
                if (!Objects.equals(outputSym.symbol(), this.modelParams.silentOutput()) ||
                    ws.timeSteps() == this.modelParams.maxTimeoutWaitingTime()) {
                    // Found a timeout OR no timeout after max_delay:
                    wbInput.append(new TimeoutSymbol<>());
                    wbOutput.append(outputSym);
                    continue;
                }

                assert ws.timeSteps() < this.modelParams.maxTimeoutWaitingTime() :
                        "Wait time that exceeds max_delay in cache.";

                // Special case: silent output before max delay
                // Cannot replace with "timeout", as this implies wait until max_delay.
                // Hence: skip subsequent waits until reaching wait with output OR max_delay OR end of word:
                long combinedWaitTime = ws.timeSteps();
                TimedOutput<O> combinedOutput = outputSym;

                while (Objects.equals(combinedOutput.symbol(), this.modelParams.silentOutput()) &&
                       combinedWaitTime < this.modelParams.maxTimeoutWaitingTime() && symIdx < queryInput.length() &&
                       queryInput.getSymbol(symIdx) instanceof TimeStepSequence<I> nextWs) {
                    combinedWaitTime += nextWs.timeSteps();
                    combinedOutput = queryOutput.getSymbol(symIdx);
                    symIdx++;
                }

                if (combinedWaitTime >= this.modelParams.maxTimeoutWaitingTime() ||
                    !Objects.equals(combinedOutput.symbol(), this.modelParams.silentOutput())) {
                    wbInput.append(new TimeoutSymbol<>());

                    if (Objects.equals(combinedOutput.symbol(), this.modelParams.silentOutput())) {
                        // Reached max delay -> waiting for any time will now produce no more timeouts:
                        wbOutput.append(new TimedOutput<>(this.modelParams.silentOutput()));
                    } else {
                        // Found non-silent output:
                        wbOutput.append(new TimedOutput<>(combinedOutput.symbol(), combinedWaitTime));
                    }
                } else {
                    // Reached end of word before max_delay OR non-wait symbol -> ignore rest of this word:
                    if (symIdx < queryInput.length() - 1) {
                        LOGGER.debug("Ignoring at least one symbol during cache comparison.");
                    }
                    break;
                }
            }
        }
        return new DefaultQuery<>(wbInput.toWord(), wbOutput.toWord());
    }

    private DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> reduceToAllowedInputs(Set<TimedInput<I>> allowedInputs,
                                                                                    DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> query) {
        // Find the longest prefix with allowed inputs:
        int prefixLength = 0;
        while (prefixLength < query.length() && allowedInputs.contains(query.getInput().getSymbol(prefixLength))) {
            prefixLength++;
        }

        if (prefixLength == query.length()) {
            return query; // maximum length -> no need to reduce
        } else {
            return new DefaultQuery<>(query.getInput().prefix(prefixLength), query.getOutput().prefix(prefixLength));
        }
    }

    @Override
    public @Nullable DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> findCounterExample(MMLT<?, I, ?, O> hypothesis,
                                                                                          Collection<? extends TimedInput<I>> inputs) {
        Set<TimedInput<I>> allowedInputs = new HashSet<>(inputs);
        boolean allInputsConsidered = allowedInputs.containsAll(hypothesis.getSemantics().getInputAlphabet());

        // Iterator over all cached words:
        Iterator<Word<TimedInput<I>>> iter = this.sulCache.allWordsIterator();

        while (iter.hasNext()) {
            Word<TimedInput<I>> word = iter.next();

            // First, query word as-is (may include wait-symbols in input):
            DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> rawCacheQuery = this.queryCache(word);

            // Next, convert query that includes wait-symbols to query with timeout-symbols:
            DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> convertedQuery = this.convertTimeSequences(rawCacheQuery);

            // The counterexample may only use a subset of the allowed inputs.
            // If so, cut the query to the prefix of the word that is allowed:
            DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> reducedQuery =
                    allInputsConsidered ? convertedQuery : this.reduceToAllowedInputs(allowedInputs, convertedQuery);

            // Finally, query hypothesis using the converted query:
            Word<TimedOutput<O>> hypOutput = hypothesis.getSemantics().computeOutput(reducedQuery.getInput());

            if (!hypOutput.equals(reducedQuery.getOutput())) {
                // Hyp gives different output than cache (= SUL):
                return reducedQuery;
            }
        }

        return null;
    }
}

1	/* Copyright (C) 2013-2025 TU Dortmund University
2	* This file is part of LearnLib <https://learnlib.de>.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package de.learnlib.filter.cache.mmlt;
17
18	import java.util.Collection;
19	import java.util.HashSet;
20	import java.util.Iterator;
21	import java.util.Objects;
22	import java.util.Set;
23
24	import de.learnlib.oracle.EquivalenceOracle.MMLTEquivalenceOracle;
25	import de.learnlib.query.DefaultQuery;
26	import de.learnlib.time.MMLTModelParams;
27	import net.automatalib.automaton.mmlt.MMLT;
28	import net.automatalib.symbol.time.InputSymbol;
29	import net.automatalib.symbol.time.TimeStepSequence;
30	import net.automatalib.symbol.time.TimedInput;
31	import net.automatalib.symbol.time.TimedOutput;
32	import net.automatalib.symbol.time.TimeoutSymbol;
33	import net.automatalib.word.Word;
34	import net.automatalib.word.WordBuilder;
35	import org.checkerframework.checker.nullness.qual.Nullable;
36	import org.slf4j.Logger;
37	import org.slf4j.LoggerFactory;
38
39	/**
40	* Searches for counterexamples by comparing the behavior of the hypothesis and the query cache. If there are multiple
41	* counterexamples, the shortest one is returned.
42	*
43	* @param <I>
44	* input symbol type (of non-delaying inputs)
45	* @param <O>
46	* output symbol type
47	*/
48	@SuppressWarnings("PMD.TestClassWithoutTestCases") // not a traditional test class
49	public class MMLTCacheConsistencyTest<I, O> implements MMLTEquivalenceOracle<I, O> {
50
51	private static final Logger LOGGER = LoggerFactory.getLogger(MMLTCacheConsistencyTest.class);	2✔
52
53	private final TimedSULTreeCache<I, O> sulCache;
54	private final MMLTModelParams<O> modelParams;
55
56	MMLTCacheConsistencyTest(TimedSULTreeCache<I, O> sulCache, MMLTModelParams<O> modelParams) {	2✔
57	this.sulCache = sulCache;	2✔
58	this.modelParams = modelParams;	2✔
59	}	2✔
60
61	private DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> queryCache(Word<TimedInput<I>> word) {
62	WordBuilder<TimedInput<I>> wbInput = new WordBuilder<>(word.length());	2✔
63	WordBuilder<TimedOutput<O>> wbOutput = new WordBuilder<>(word.length());	2✔
64
65	this.sulCache.pre();	2✔
66	for (TimedInput<I> sym : word) {	2✔
67	if (sym instanceof InputSymbol<I> ndi) {	2✔
68	TimedOutput<O> res = this.sulCache.step(ndi);	2✔
69	wbInput.append(ndi);	2✔
70	wbOutput.append(res);	2✔
71	} else if (sym instanceof TimeStepSequence<I> ws) {	2✔
72	TimedOutput<O> res = this.sulCache.timeoutStep(ws.timeSteps());	2✔
73	wbInput.append(ws);	2✔
74
75	if (res == null) {	2✔
76	wbOutput.append(new TimedOutput<>(this.modelParams.silentOutput()));	2✔
77	} else {
78	wbOutput.append(res);	2✔
79	}
80	} else {	2✔
NEW 81	throw new IllegalArgumentException("Symbol type " + sym.getClass() + " must not be used in cache.");	×
82	}
83	}	2✔
84	this.sulCache.post();	2✔
85
86	return new DefaultQuery<>(wbInput.toWord(), wbOutput.toWord());	2✔
87	}
88
89	/**
90	* The cache does not use timeout symbols. Using these instead of time-step-sequences has several performance
91	* benefits. This function converts a query with a time-step-sequence to one that uses timeout symbols where
92	* possible.
93	*
94	* @param originalQuery
95	* the original query
96	*
97	* @return the converted query
98	*/
99	private DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> convertTimeSequences(DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> originalQuery) {
100	WordBuilder<TimedInput<I>> wbInput = new WordBuilder<>();	2✔
101	WordBuilder<TimedOutput<O>> wbOutput = new WordBuilder<>();	2✔
102
103	int symIdx = 0;	2✔
104	Word<TimedInput<I>> queryInput = originalQuery.getInput();	2✔
105	Word<TimedOutput<O>> queryOutput = originalQuery.getOutput();	2✔
106
107	while (symIdx < queryInput.length()) {	2✔
108	TimedInput<I> inputSym = queryInput.getSymbol(symIdx);	2✔
109	TimedOutput<O> outputSym = queryOutput.getSymbol(symIdx);	2✔
110	symIdx++;	2✔
111
112	if (inputSym instanceof InputSymbol<I> ds) {	2✔
113	wbInput.append(ds);	2✔
114	wbOutput.append(outputSym);	2✔
115	} else if (inputSym instanceof TimeStepSequence<I> ws) {	2✔
116	if (!Objects.equals(outputSym.symbol(), this.modelParams.silentOutput()) \|\|	2✔
117	ws.timeSteps() == this.modelParams.maxTimeoutWaitingTime()) {	2✔
118	// Found a timeout OR no timeout after max_delay:
119	wbInput.append(new TimeoutSymbol<>());	1✔
120	wbOutput.append(outputSym);	1✔
121	continue;	1✔
122	}
123
124	assert ws.timeSteps() < this.modelParams.maxTimeoutWaitingTime() :	2✔
125	"Wait time that exceeds max_delay in cache.";
126
127	// Special case: silent output before max delay
128	// Cannot replace with "timeout", as this implies wait until max_delay.
129	// Hence: skip subsequent waits until reaching wait with output OR max_delay OR end of word:
130	long combinedWaitTime = ws.timeSteps();	2✔
131	TimedOutput<O> combinedOutput = outputSym;	2✔
132
133	while (Objects.equals(combinedOutput.symbol(), this.modelParams.silentOutput()) &&	2✔
134	combinedWaitTime < this.modelParams.maxTimeoutWaitingTime() && symIdx < queryInput.length() &&	2✔
135	queryInput.getSymbol(symIdx) instanceof TimeStepSequence<I> nextWs) {	2✔
136	combinedWaitTime += nextWs.timeSteps();	2✔
137	combinedOutput = queryOutput.getSymbol(symIdx);	2✔
138	symIdx++;	2✔
139	}
140
141	if (combinedWaitTime >= this.modelParams.maxTimeoutWaitingTime() \|\|	2✔
142	!Objects.equals(combinedOutput.symbol(), this.modelParams.silentOutput())) {	2✔
143	wbInput.append(new TimeoutSymbol<>());	2✔
144
145	if (Objects.equals(combinedOutput.symbol(), this.modelParams.silentOutput())) {	2✔
146	// Reached max delay -> waiting for any time will now produce no more timeouts:
147	wbOutput.append(new TimedOutput<>(this.modelParams.silentOutput()));	2✔
148	} else {
149	// Found non-silent output:
150	wbOutput.append(new TimedOutput<>(combinedOutput.symbol(), combinedWaitTime));	2✔
151	}
152	} else {
153	// Reached end of word before max_delay OR non-wait symbol -> ignore rest of this word:
154	if (symIdx < queryInput.length() - 1) {	2✔
155	LOGGER.debug("Ignoring at least one symbol during cache comparison.");	2✔
156	}
157	break;
158	}
159	}
160	}	2✔
161	return new DefaultQuery<>(wbInput.toWord(), wbOutput.toWord());	2✔
162	}
163
164	private DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> reduceToAllowedInputs(Set<TimedInput<I>> allowedInputs,
165	DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> query) {
166	// Find the longest prefix with allowed inputs:
167	int prefixLength = 0;	2✔
168	while (prefixLength < query.length() && allowedInputs.contains(query.getInput().getSymbol(prefixLength))) {	2✔
169	prefixLength++;	2✔
170	}
171
172	if (prefixLength == query.length()) {	2✔
173	return query; // maximum length -> no need to reduce	2✔
174	} else {
175	return new DefaultQuery<>(query.getInput().prefix(prefixLength), query.getOutput().prefix(prefixLength));	2✔
176	}
177	}
178
179	@Override
180	public @Nullable DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> findCounterExample(MMLT<?, I, ?, O> hypothesis,
181	Collection<? extends TimedInput<I>> inputs) {
182	Set<TimedInput<I>> allowedInputs = new HashSet<>(inputs);	2✔
183	boolean allInputsConsidered = allowedInputs.containsAll(hypothesis.getSemantics().getInputAlphabet());	2✔
184
185	// Iterator over all cached words:
186	Iterator<Word<TimedInput<I>>> iter = this.sulCache.allWordsIterator();	2✔
187
188	while (iter.hasNext()) {	2✔
189	Word<TimedInput<I>> word = iter.next();	2✔
190
191	// First, query word as-is (may include wait-symbols in input):
192	DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> rawCacheQuery = this.queryCache(word);	2✔
193
194	// Next, convert query that includes wait-symbols to query with timeout-symbols:
195	DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> convertedQuery = this.convertTimeSequences(rawCacheQuery);	2✔
196
197	// The counterexample may only use a subset of the allowed inputs.
198	// If so, cut the query to the prefix of the word that is allowed:
199	DefaultQuery<TimedInput<I>, Word<TimedOutput<O>>> reducedQuery =
200	allInputsConsidered ? convertedQuery : this.reduceToAllowedInputs(allowedInputs, convertedQuery);	2✔
201
202	// Finally, query hypothesis using the converted query:
203	Word<TimedOutput<O>> hypOutput = hypothesis.getSemantics().computeOutput(reducedQuery.getInput());	2✔
204
205	if (!hypOutput.equals(reducedQuery.getOutput())) {	2✔
206	// Hyp gives different output than cache (= SUL):
207	return reducedQuery;	2✔
208	}
209	}	2✔
210
211	return null;	2✔
212	}
213	}

LearnLib / learnlib / 20198569605

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous