6433387082

Committed 06 Oct 2023 03:10PM UTC coverage: 92.296% (-0.007%) from 92.303%

Build # 6433387082

Build Type

push

github

Committed by

mtf90

Commit Message

update Falk's developer id

Run Details

11573 of 12539 relevant lines covered (92.3%)

1.67 hits per line

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

90.63

/oracles/equivalence-oracles/src/main/java/de/learnlib/oracle/equivalence/RandomWMethodEQOracle.java

/* Copyright (C) 2013-2023 TU Dortmund
 * This file is part of LearnLib, http://www.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.oracle.equivalence;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Random;
import java.util.stream.Stream;

import de.learnlib.api.oracle.EquivalenceOracle.DFAEquivalenceOracle;
import de.learnlib.api.oracle.EquivalenceOracle.MealyEquivalenceOracle;
import de.learnlib.api.oracle.EquivalenceOracle.MooreEquivalenceOracle;
import de.learnlib.api.oracle.MembershipOracle;
import de.learnlib.api.oracle.MembershipOracle.DFAMembershipOracle;
import de.learnlib.api.oracle.MembershipOracle.MealyMembershipOracle;
import de.learnlib.api.oracle.MembershipOracle.MooreMembershipOracle;
import de.learnlib.buildtool.refinement.annotation.GenerateRefinement;
import de.learnlib.buildtool.refinement.annotation.Generic;
import de.learnlib.buildtool.refinement.annotation.Interface;
import de.learnlib.buildtool.refinement.annotation.Map;
import net.automatalib.automata.UniversalDeterministicAutomaton;
import net.automatalib.automata.concepts.Output;
import net.automatalib.automata.fsa.DFA;
import net.automatalib.automata.transducers.MealyMachine;
import net.automatalib.automata.transducers.MooreMachine;
import net.automatalib.util.automata.Automata;
import net.automatalib.util.automata.cover.Covers;
import net.automatalib.words.Word;
import net.automatalib.words.WordBuilder;

/**
 * Implements an equivalence test by applying the W-method test on the given hypothesis automaton. Generally the
 * Wp-method performs better in finding counter examples. Instead of enumerating the test suite in order, this is a
 * sampling implementation:
 * <ul>
 * <li>1. sample uniformly from the transitions for a prefix</li>
 * <li>2. sample geometrically a random word</li>
 * <li>3. sample a word from the set of suffixes / state identifiers</li>
 * </ul>
 * There are two parameters: minimalSize determines the minimal size of the random word, this is useful when one first
 * performs a W(p)-method with some depth and continue with this randomized tester from that depth onward. The second
 * parameter rndLength determines the expected length of the random word. (The expected length in effect is minimalSize
 * + rndLength.) In the unbounded case it will not terminate for a correct hypothesis.
 *
 * @param <A>
 *         automaton type
 * @param <I>
 *         input symbol type
 * @param <D>
 *         output domain type
 */
@GenerateRefinement(name = "DFARandomWMethodEQOracle",
                    generics = "I",
                    parentGenerics = {@Generic(clazz = DFA.class, generics = {"?", "I"}),
                                      @Generic("I"),
                                      @Generic(clazz = Boolean.class)},
                    parameterMapping = @Map(from = MembershipOracle.class,
                                            to = DFAMembershipOracle.class,
                                            withGenerics = "I"),
                    interfaces = @Interface(clazz = DFAEquivalenceOracle.class, generics = "I"))
@GenerateRefinement(name = "MealyRandomWMethodEQOracle",
                    generics = {"I", "O"},
                    parentGenerics = {@Generic(clazz = MealyMachine.class, generics = {"?", "I", "?", "O"}),
                                      @Generic("I"),
                                      @Generic(clazz = Word.class, generics = "O")},
                    parameterMapping = @Map(from = MembershipOracle.class,
                                            to = MealyMembershipOracle.class,
                                            withGenerics = {"I", "O"}),
                    interfaces = @Interface(clazz = MealyEquivalenceOracle.class, generics = {"I", "O"}))
@GenerateRefinement(name = "MooreRandomWMethodEQOracle",
                    generics = {"I", "O"},
                    parentGenerics = {@Generic(clazz = MooreMachine.class, generics = {"?", "I", "?", "O"}),
                                      @Generic("I"),
                                      @Generic(clazz = Word.class, generics = "O")},
                    parameterMapping = @Map(from = MembershipOracle.class,
                                            to = MooreMembershipOracle.class,
                                            withGenerics = {"I", "O"}),
                    interfaces = @Interface(clazz = MooreEquivalenceOracle.class, generics = {"I", "O"}))
public class RandomWMethodEQOracle<A extends UniversalDeterministicAutomaton<?, I, ?, ?, ?> & Output<I, D>, I, D>
        extends AbstractTestWordEQOracle<A, I, D> {

    private final int minimalSize;
    private final int rndLength;
    private final int bound;
    private final Random rand;

    /**
     * Constructor for an unbounded testing oracle.
     *
     * @param sulOracle
     *         oracle which answers tests.
     * @param minimalSize
     *         minimal size of the random word
     * @param rndLength
     *         expected length (in addition to minimalSize) of random word
     */
    public RandomWMethodEQOracle(MembershipOracle<I, D> sulOracle, int minimalSize, int rndLength) {
        this(sulOracle, minimalSize, rndLength, 0);
    }

    /**
     * Constructor for a bounded testing oracle.
     *
     * @param sulOracle
     *         oracle which answers tests.
     * @param minimalSize
     *         minimal size of the random word
     * @param rndLength
     *         expected length (in addition to minimalSize) of random word
     * @param bound
     *         specifies the bound (set to 0 for unbounded).
     */
    public RandomWMethodEQOracle(MembershipOracle<I, D> sulOracle, int minimalSize, int rndLength, int bound) {
        this(sulOracle, minimalSize, rndLength, bound, 1);
    }

    /**
     * Constructor for a bounded testing oracle with a specific batch size.
     *
     * @param sulOracle
     *         oracle which answers tests.
     * @param minimalSize
     *         minimal size of the random word
     * @param rndLength
     *         expected length (in addition to minimalSize) of random word
     * @param bound
     *         specifies the bound (set to 0 for unbounded).
     * @param batchSize
     *         size of the batches sent to the membership oracle
     */
    public RandomWMethodEQOracle(MembershipOracle<I, D> sulOracle,
                                 int minimalSize,
                                 int rndLength,
                                 int bound,
                                 int batchSize) {
        this(sulOracle, minimalSize, rndLength, bound, new Random(), batchSize);
    }

    /**
     * Constructor for a bounded testing oracle with a specific batch size.
     *
     * @param sulOracle
     *         oracle which answers tests.
     * @param minimalSize
     *         minimal size of the random word
     * @param rndLength
     *         expected length (in addition to minimalSize) of random word
     * @param bound
     *         specifies the bound (set to 0 for unbounded).
     * @param random
     *         custom Random generator.
     * @param batchSize
     *         size of the batches sent to the membership oracle
     */
    public RandomWMethodEQOracle(MembershipOracle<I, D> sulOracle,
                                 int minimalSize,
                                 int rndLength,
                                 int bound,
                                 Random random,
                                 int batchSize) {
        super(sulOracle, batchSize);
        this.minimalSize = minimalSize;
        this.rndLength = rndLength;
        this.bound = bound;
        this.rand = random;
    }

    @Override
    protected Stream<Word<I>> generateTestWords(A hypothesis, Collection<? extends I> inputs) {
        UniversalDeterministicAutomaton<?, I, ?, ?, ?> aut = hypothesis;
        return doGenerateTestWords(aut, inputs);
    }

    /*
     * Delegate target, used to bind the state-parameter of the automaton
     */
    private <S> Stream<Word<I>> doGenerateTestWords(UniversalDeterministicAutomaton<S, I, ?, ?, ?> hypothesis,
                                                    Collection<? extends I> inputs) {
        // Note that we want to use ArrayLists because we want constant time random access
        // We will sample from this for a prefix
        List<Word<I>> transitionCover = new ArrayList<>(hypothesis.size());
        Covers.transitionCover(hypothesis, inputs, transitionCover);

        // Then repeatedly from this for a random word
        List<I> arrayAlphabet = new ArrayList<>(inputs);

        // Finally we test the state with a suffix
        List<Word<I>> globalSuffixes = new ArrayList<>();
        Automata.characterizingSet(hypothesis, inputs, globalSuffixes);

        final Stream<Word<I>> result =
                Stream.generate(() -> generateSingleTestWord(transitionCover, arrayAlphabet, globalSuffixes));

        return bound > 0 ? result.limit(bound) : result;
    }

    private Word<I> generateSingleTestWord(List<Word<I>> stateCover,
                                           List<I> arrayAlphabet,
                                           List<Word<I>> globalSuffixes) {
        final WordBuilder<I> wb = new WordBuilder<>(minimalSize + rndLength + 1);

        // pick a random state
        wb.append(stateCover.get(rand.nextInt(stateCover.size())));

        // construct random middle part (of some expected length)
        int size = minimalSize;
        while (size > 0 || rand.nextDouble() > 1 / (rndLength + 1.0)) {
            wb.append(arrayAlphabet.get(rand.nextInt(arrayAlphabet.size())));
            if (size > 0) {
                size--;
            }
        }

        // pick a random suffix for this state
        if (!globalSuffixes.isEmpty()) {
            wb.append(globalSuffixes.get(rand.nextInt(globalSuffixes.size())));
        }

        return wb.toWord();
    }
}

1	/* Copyright (C) 2013-2023 TU Dortmund
2	* This file is part of LearnLib, http://www.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.oracle.equivalence;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.List;
21	import java.util.Random;
22	import java.util.stream.Stream;
23
24	import de.learnlib.api.oracle.EquivalenceOracle.DFAEquivalenceOracle;
25	import de.learnlib.api.oracle.EquivalenceOracle.MealyEquivalenceOracle;
26	import de.learnlib.api.oracle.EquivalenceOracle.MooreEquivalenceOracle;
27	import de.learnlib.api.oracle.MembershipOracle;
28	import de.learnlib.api.oracle.MembershipOracle.DFAMembershipOracle;
29	import de.learnlib.api.oracle.MembershipOracle.MealyMembershipOracle;
30	import de.learnlib.api.oracle.MembershipOracle.MooreMembershipOracle;
31	import de.learnlib.buildtool.refinement.annotation.GenerateRefinement;
32	import de.learnlib.buildtool.refinement.annotation.Generic;
33	import de.learnlib.buildtool.refinement.annotation.Interface;
34	import de.learnlib.buildtool.refinement.annotation.Map;
35	import net.automatalib.automata.UniversalDeterministicAutomaton;
36	import net.automatalib.automata.concepts.Output;
37	import net.automatalib.automata.fsa.DFA;
38	import net.automatalib.automata.transducers.MealyMachine;
39	import net.automatalib.automata.transducers.MooreMachine;
40	import net.automatalib.util.automata.Automata;
41	import net.automatalib.util.automata.cover.Covers;
42	import net.automatalib.words.Word;
43	import net.automatalib.words.WordBuilder;
44
45	/**
46	* Implements an equivalence test by applying the W-method test on the given hypothesis automaton. Generally the
47	* Wp-method performs better in finding counter examples. Instead of enumerating the test suite in order, this is a
48	* sampling implementation:
49	* <ul>
50	* <li>1. sample uniformly from the transitions for a prefix</li>
51	* <li>2. sample geometrically a random word</li>
52	* <li>3. sample a word from the set of suffixes / state identifiers</li>
53	* </ul>
54	* There are two parameters: minimalSize determines the minimal size of the random word, this is useful when one first
55	* performs a W(p)-method with some depth and continue with this randomized tester from that depth onward. The second
56	* parameter rndLength determines the expected length of the random word. (The expected length in effect is minimalSize
57	* + rndLength.) In the unbounded case it will not terminate for a correct hypothesis.
58	*
59	* @param <A>
60	* automaton type
61	* @param <I>
62	* input symbol type
63	* @param <D>
64	* output domain type
65	*/
66	@GenerateRefinement(name = "DFARandomWMethodEQOracle",
67	generics = "I",
68	parentGenerics = {@Generic(clazz = DFA.class, generics = {"?", "I"}),
69	@Generic("I"),
70	@Generic(clazz = Boolean.class)},
71	parameterMapping = @Map(from = MembershipOracle.class,
72	to = DFAMembershipOracle.class,
73	withGenerics = "I"),
74	interfaces = @Interface(clazz = DFAEquivalenceOracle.class, generics = "I"))
75	@GenerateRefinement(name = "MealyRandomWMethodEQOracle",
76	generics = {"I", "O"},
77	parentGenerics = {@Generic(clazz = MealyMachine.class, generics = {"?", "I", "?", "O"}),
78	@Generic("I"),
79	@Generic(clazz = Word.class, generics = "O")},
80	parameterMapping = @Map(from = MembershipOracle.class,
81	to = MealyMembershipOracle.class,
82	withGenerics = {"I", "O"}),
83	interfaces = @Interface(clazz = MealyEquivalenceOracle.class, generics = {"I", "O"}))
84	@GenerateRefinement(name = "MooreRandomWMethodEQOracle",
85	generics = {"I", "O"},
86	parentGenerics = {@Generic(clazz = MooreMachine.class, generics = {"?", "I", "?", "O"}),
87	@Generic("I"),
88	@Generic(clazz = Word.class, generics = "O")},
89	parameterMapping = @Map(from = MembershipOracle.class,
90	to = MooreMembershipOracle.class,
91	withGenerics = {"I", "O"}),
92	interfaces = @Interface(clazz = MooreEquivalenceOracle.class, generics = {"I", "O"}))
93	public class RandomWMethodEQOracle<A extends UniversalDeterministicAutomaton<?, I, ?, ?, ?> & Output<I, D>, I, D>
94	extends AbstractTestWordEQOracle<A, I, D> {
95
96	private final int minimalSize;
97	private final int rndLength;
98	private final int bound;
99	private final Random rand;
100
101	/**
102	* Constructor for an unbounded testing oracle.
103	*
104	* @param sulOracle
105	* oracle which answers tests.
106	* @param minimalSize
107	* minimal size of the random word
108	* @param rndLength
109	* expected length (in addition to minimalSize) of random word
110	*/
111	public RandomWMethodEQOracle(MembershipOracle<I, D> sulOracle, int minimalSize, int rndLength) {
112	this(sulOracle, minimalSize, rndLength, 0);	×
113	}	×
114
115	/**
116	* Constructor for a bounded testing oracle.
117	*
118	* @param sulOracle
119	* oracle which answers tests.
120	* @param minimalSize
121	* minimal size of the random word
122	* @param rndLength
123	* expected length (in addition to minimalSize) of random word
124	* @param bound
125	* specifies the bound (set to 0 for unbounded).
126	*/
127	public RandomWMethodEQOracle(MembershipOracle<I, D> sulOracle, int minimalSize, int rndLength, int bound) {
128	this(sulOracle, minimalSize, rndLength, bound, 1);	2✔
129	}	2✔
130
131	/**
132	* Constructor for a bounded testing oracle with a specific batch size.
133	*
134	* @param sulOracle
135	* oracle which answers tests.
136	* @param minimalSize
137	* minimal size of the random word
138	* @param rndLength
139	* expected length (in addition to minimalSize) of random word
140	* @param bound
141	* specifies the bound (set to 0 for unbounded).
142	* @param batchSize
143	* size of the batches sent to the membership oracle
144	*/
145	public RandomWMethodEQOracle(MembershipOracle<I, D> sulOracle,
146	int minimalSize,
147	int rndLength,
148	int bound,
149	int batchSize) {
150	this(sulOracle, minimalSize, rndLength, bound, new Random(), batchSize);	2✔
151	}	2✔
152
153	/**
154	* Constructor for a bounded testing oracle with a specific batch size.
155	*
156	* @param sulOracle
157	* oracle which answers tests.
158	* @param minimalSize
159	* minimal size of the random word
160	* @param rndLength
161	* expected length (in addition to minimalSize) of random word
162	* @param bound
163	* specifies the bound (set to 0 for unbounded).
164	* @param random
165	* custom Random generator.
166	* @param batchSize
167	* size of the batches sent to the membership oracle
168	*/
169	public RandomWMethodEQOracle(MembershipOracle<I, D> sulOracle,
170	int minimalSize,
171	int rndLength,
172	int bound,
173	Random random,
174	int batchSize) {
175	super(sulOracle, batchSize);	2✔
176	this.minimalSize = minimalSize;	2✔
177	this.rndLength = rndLength;	2✔
178	this.bound = bound;	2✔
179	this.rand = random;	2✔
180	}	2✔
181
182	@Override
183	protected Stream<Word<I>> generateTestWords(A hypothesis, Collection<? extends I> inputs) {
184	UniversalDeterministicAutomaton<?, I, ?, ?, ?> aut = hypothesis;	2✔
185	return doGenerateTestWords(aut, inputs);	2✔
186	}
187
188	/*
189	* Delegate target, used to bind the state-parameter of the automaton
190	*/
191	private <S> Stream<Word<I>> doGenerateTestWords(UniversalDeterministicAutomaton<S, I, ?, ?, ?> hypothesis,
192	Collection<? extends I> inputs) {
193	// Note that we want to use ArrayLists because we want constant time random access
194	// We will sample from this for a prefix
195	List<Word<I>> transitionCover = new ArrayList<>(hypothesis.size());	2✔
196	Covers.transitionCover(hypothesis, inputs, transitionCover);	2✔
197
198	// Then repeatedly from this for a random word
199	List<I> arrayAlphabet = new ArrayList<>(inputs);	2✔
200
201	// Finally we test the state with a suffix
202	List<Word<I>> globalSuffixes = new ArrayList<>();	2✔
203	Automata.characterizingSet(hypothesis, inputs, globalSuffixes);	2✔
204
205	final Stream<Word<I>> result =	2✔
206	Stream.generate(() -> generateSingleTestWord(transitionCover, arrayAlphabet, globalSuffixes));	2✔
207
208	return bound > 0 ? result.limit(bound) : result;	2✔
209	}
210
211	private Word<I> generateSingleTestWord(List<Word<I>> stateCover,
212	List<I> arrayAlphabet,
213	List<Word<I>> globalSuffixes) {
214	final WordBuilder<I> wb = new WordBuilder<>(minimalSize + rndLength + 1);	2✔
215
216	// pick a random state
217	wb.append(stateCover.get(rand.nextInt(stateCover.size())));	2✔
218
219	// construct random middle part (of some expected length)
220	int size = minimalSize;	2✔
221	while (size > 0 \|\| rand.nextDouble() > 1 / (rndLength + 1.0)) {	2✔
222	wb.append(arrayAlphabet.get(rand.nextInt(arrayAlphabet.size())));	2✔
223	if (size > 0) {	2✔
224	size--;	×
225	}
226	}
227
228	// pick a random suffix for this state
229	if (!globalSuffixes.isEmpty()) {	2✔
230	wb.append(globalSuffixes.get(rand.nextInt(globalSuffixes.size())));	2✔
231	}
232
233	return wb.toWord();	2✔
234	}
235	}

LearnLib / learnlib / 6433387082

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