001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of LearnLib, http://www.learnlib.de/. 003 * 004 * LearnLib is free software; you can redistribute it and/or 005 * modify it under the terms of the GNU Lesser General Public 006 * License version 3.0 as published by the Free Software Foundation. 007 * 008 * LearnLib is distributed in the hope that it will be useful, 009 * but WITHOUT ANY WARRANTY; without even the implied warranty of 010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 011 * Lesser General Public License for more details. 012 * 013 * You should have received a copy of the GNU Lesser General Public 014 * License along with LearnLib; if not, see 015 * <http://www.gnu.de/documents/lgpl.en.html>. 016 */ 017package de.learnlib.examples.example2; 018 019import java.io.IOException; 020import java.io.Writer; 021import java.lang.reflect.InvocationTargetException; 022import java.lang.reflect.Method; 023import java.util.ArrayDeque; 024import java.util.ArrayList; 025import java.util.Arrays; 026import java.util.Deque; 027import java.util.List; 028import java.util.Random; 029 030import net.automatalib.automata.transout.MealyMachine; 031import net.automatalib.commons.dotutil.DOT; 032import net.automatalib.util.graphs.dot.GraphDOT; 033import net.automatalib.words.Alphabet; 034import net.automatalib.words.Word; 035import net.automatalib.words.impl.SimpleAlphabet; 036import de.learnlib.algorithms.lstargeneric.ce.ObservationTableCEXHandlers; 037import de.learnlib.algorithms.lstargeneric.closing.ClosingStrategies; 038import de.learnlib.algorithms.lstargeneric.mealy.ExtensibleLStarMealy; 039import de.learnlib.api.EquivalenceOracle.MealyEquivalenceOracle; 040import de.learnlib.api.LearningAlgorithm.MealyLearner; 041import de.learnlib.api.SUL; 042import de.learnlib.cache.Caches; 043import de.learnlib.eqtests.basic.mealy.RandomWalkEQOracle; 044import de.learnlib.experiments.Experiment.MealyExperiment; 045import de.learnlib.oracles.ResetCounterSUL; 046import de.learnlib.oracles.SULOracle; 047import de.learnlib.statistics.SimpleProfiler; 048import de.learnlib.statistics.StatisticSUL; 049 050/** 051 * This example shows how a model of a Java class can be learned using the SUL 052 * (system under learning) interfaces and the random walks equivalence test. 053 * 054 * @author falkhowar 055 */ 056public class Example { 057 058 /* 059 * The BoundedStringQueue is the class of which we are going to 060 * infer a model. It wraps an ordinary queue of Strings, limiting 061 * its size to MAX_SIZE (3). Once the queue is full, additional 062 * offers will be ignored. 063 * <p> 064 * However, the implementation uses the underlying queue in a strange 065 * way as the model will reveal. 066 */ 067 public static class BoundedStringQueue { 068 069 // capacity 070 public static final int MAX_SIZE = 3; 071 // storage 072 private Deque<String> data = new ArrayDeque<>(3); 073 074 // add a String to the queue if capacity allows 075 public void offer(String s) { 076 if (data.size() < MAX_SIZE) { 077 data.offerFirst(s); 078 } 079 } 080 081 // get next element from queue (null for empty queue) 082 public String poll() { 083 return data.poll(); 084 } 085 } 086 087 /* 088 * We use the BSQInput class to wrap concrete method invocations 089 * and use these as alphabet symbols for the learning algorithm 090 */ 091 public static class BSQInput { 092 093 // method to invoke 094 public final Method action; 095 096 // method parameter values 097 public final Object[] data; 098 099 public BSQInput(Method action, Object[] data) { 100 this.action = action; 101 this.data = data; 102 } 103 104 // this will be used for printing when 105 // logging or exporting automata 106 @Override 107 public String toString() { 108 return action.getName() + Arrays.toString(data); 109 } 110 } 111 112 /* 113 * The BSQAdapter 114 * 115 */ 116 public static class BSQAdapter implements SUL<BSQInput, String> { 117 118 // system under learning 119 private BoundedStringQueue sul; 120 121 // reset the SUL 122 @Override 123 public void reset() { 124 // we just create a new instance 125 sul = new BoundedStringQueue(); 126 } 127 128 // execute one input on the SUL 129 @Override 130 public String step(BSQInput in) { 131 try { 132 // invoke the method wrapped by in 133 Object ret = in.action.invoke(sul, in.data); 134 // make sure that we return a string 135 return ret == null ? "" : (String) ret; 136 } 137 catch (IllegalAccessException | 138 IllegalArgumentException | 139 InvocationTargetException e) { 140 // This should never happen. In a real experiment 141 // this would be the point when we want to issue 142 // a warning or stop the learning. 143 return "err"; 144 } 145 } 146 } 147 148 public static void main(String[] args) throws NoSuchMethodException, IOException { 149 150 // create learning alphabet 151 152 // offer(a) 153 BSQInput offer_a = new BSQInput(BoundedStringQueue.class.getMethod( 154 "offer", new Class<?>[]{String.class}), new Object[]{"a"}); 155 156 // offer(b) 157 BSQInput offer_b = new BSQInput(BoundedStringQueue.class.getMethod( 158 "offer", new Class<?>[]{String.class}), new Object[]{"b"}); 159 160 // poll() 161 BSQInput poll = new BSQInput(BoundedStringQueue.class.getMethod( 162 "poll", new Class<?>[]{}), new Object[]{}); 163 164 Alphabet<BSQInput> inputs = new SimpleAlphabet<>(); 165 inputs.add(offer_a); 166 inputs.add(offer_b); 167 inputs.add(poll); 168 169 // create an oracle that can answer membership queries 170 // using the BSQAdapter 171 SUL<BSQInput,String> sul = new BSQAdapter(); 172 173 // oracle for counting queries wraps sul 174 StatisticSUL<BSQInput, String> statisticSul = new ResetCounterSUL<>("membership queries", sul); 175 176 SUL<BSQInput,String> effectiveSul = statisticSul; 177 // use caching in order to avoid duplicate queries 178 effectiveSul = Caches.createSULCache(inputs, effectiveSul); 179 180 SULOracle<BSQInput, String> mqOracle = new SULOracle<>(effectiveSul); 181 182 // create initial set of suffixes 183 List<Word<BSQInput>> suffixes = new ArrayList<>(); 184 suffixes.add(Word.fromSymbols(offer_a)); 185 suffixes.add(Word.fromSymbols(offer_b)); 186 suffixes.add(Word.fromSymbols(poll)); 187 188 // construct L* instance (almost classic Mealy version) 189 // almost: we use words (Word<String>) in cells of the table 190 // instead of single outputs. 191 MealyLearner<BSQInput,String> lstar = 192 new ExtensibleLStarMealy<>( 193 inputs, // input alphabet 194 mqOracle, // mq oracle 195 suffixes, // initial suffixes 196 ObservationTableCEXHandlers.CLASSIC_LSTAR, // handling of counterexamples 197 ClosingStrategies.CLOSE_FIRST // always choose first unclosedness found 198 ); 199 200 // create random walks equivalence test 201 MealyEquivalenceOracle<BSQInput,String> randomWalks = 202 new RandomWalkEQOracle<>( 203 0.05, // reset SUL w/ this probability before a step 204 10000, // max steps (overall) 205 false, // reset step count after counterexample 206 new Random(46346293), // make results reproducible 207 sul // system under learning 208 ); 209 210 // construct a learning experiment from 211 // the learning algorithm and the random walks test. 212 // The experiment will execute the main loop of 213 // active learning 214 MealyExperiment<BSQInput,String> experiment = 215 new MealyExperiment<>(lstar, randomWalks, inputs); 216 217 // turn on time profiling 218 experiment.setProfile(true); 219 220 // enable logging of models 221 experiment.setLogModels(true); 222 223 // run experiment 224 experiment.run(); 225 226 // get learned model 227 MealyMachine<?, BSQInput, ?, String> result = experiment.getFinalHypothesis(); 228 229 // report results 230 System.out.println("-------------------------------------------------------"); 231 232 // profiling 233 System.out.println(SimpleProfiler.getResults()); 234 235 // learning statistics 236 System.out.println(experiment.getRounds().getSummary()); 237 System.out.println(statisticSul.getStatisticalData().getSummary()); 238 239 // model statistics 240 System.out.println("States: " + result.size()); 241 System.out.println("Sigma: " + inputs.size()); 242 243 // show model 244 System.out.println(); 245 System.out.println("Model: "); 246 247 GraphDOT.write(result, inputs, System.out); // may throw IOException! 248 Writer w = DOT.createDotWriter(true); 249 GraphDOT.write(result, inputs, w); 250 w.close(); 251 252 System.out.println("-------------------------------------------------------"); 253 254 } 255}