Abstract-Problemet att avgöra om ett observerat beteende är acceptabelt är orakel problemet. När man testar från en ändlig tillståndsmaskin (FSM), är det lätt att lösa oraklet problem och så har det fått relativt lite uppmärksamhet för FSMs. Men om systemet under test har fysiskt distribuerade gränssnitt, kallas portar, sedan i distribuerad testning, observerar vi ett lokalt spår vid varje port och vi jämför uppsättningen av lokala spår med uppsättningen tillåtna beteenden (globala spår). I detta dokument undersöks orakelproblemet för deterministiska och icke-deterministiska FSM och för två alternativa definitioner av överensstämmelse för distribuerad testning. Vi visar att oraklet problemet kan lösas i polynom tid för den svagare begreppet konformitet (v w ) men är NP-hård för den starkare begreppet konformitet (v s ), även om FSM är deterministisk. Men när man testar från en deterministisk FSM med kontrollerbara ingångssekvenser, kan oraklet problemet lösas i polynom tid och liknande resultat hålla för icke-deterministiska FSM. I vissa fall kan alltså orakelproblemet lösas effektivt vid användning av v s och där så inte är fallet kan vi använda beslutsförfarandet för v w som en sund approximation. Index Terms-software engineering/software/programverifiering, programvaruteknik/testning och felsökning, system och programvara, distribuerade system, ändlig tillstånd maskin, icke-determinism, test oracle, kontrollerbarhet, lokal observerbarhet.
Ett tidigare arbete visade att Oracle problemet är NP-hård för distribuerad testning men detta gällde testning från en FSM REF.
Oracles for Distributed Testing
{'venue': 'IEEE Transactions on Software Engineering', 'journal': 'IEEE Transactions on Software Engineering', 'mag_field_of_study': ['Computer Science']}