💻 computer science

Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs

Dit artikel analyseert de computationele complexiteit van het vinden van een testset voor edge coverage in control flow graphs met extra constraints, waarbij het aantoont dat het probleem voor positieve constraints in polynomiale tijd oplosbaar is, maar voor negatieve, exacte, maximaal-een en altijd-constraints NP-compleet blijft, hoewel er een FPT-algoritme bestaat voor het geval van negatieve constraints.

Oorspronkelijke auteurs: Jakub Ruszil, Artur Polański, Adam Roman, Jakub Zelek

Gepubliceerd 2026-02-24

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Jakub Ruszil, Artur Polański, Adam Roman, Jakub Zelek

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Kern: Het "Onmogelijke" Testen van Software

Stel je voor dat je een heel groot, complex gebouw (een softwareprogramma) moet inspecteren. Je bent de veiligheidscontroleur. Je wilt zeker weten dat elke deur, elk raam en elke gang (in de programmeertaal: elke edge of verbinding) minstens één keer wordt bezocht door een inspecteur. Dit noemen we Edge Coverage.

In de wereld van softwaretesten gebruiken ze vaak een kaart van het gebouw: een Stroomdiagram (Control Flow Graph). Deze kaart toont alle mogelijke routes die een gebruiker kan nemen.

Het Probleem: De "Semantische Kloof"
Het probleem is dat deze kaarten vaak te vrijgevig zijn. Ze laten routes zien die in de echte wereld onmogelijk zijn.

Voorbeeld: De kaart zegt dat je eerst de kelder kunt inlopen en daarna de zolder, zonder tussenkomst. In de echte wereld is dat onmogelijk omdat de trap ontbreekt of omdat je eerst een sleutel nodig hebt.
Als je je alleen op de kaart verlaat, zou je kunnen proberen een test te schrijven voor een route die nooit bestaat. Dat is tijdverspilling en kan leiden tot verkeerde conclusies.

Om dit op te lossen, voegen de auteurs beperkingen (constraints) toe aan de kaart. Dit zijn regels die zeggen: "Je mag dit niet doen" of "Je moet dit altijd doen".

De Vijf Regels (De "Verkeersborden")

De auteurs kijken naar vijf soorten regels die ze aan de kaart kunnen hangen:

POSITIVE (De "Moet-Regel"):
- Regel: "Na het passeren van de poort, moet je minstens één keer de bibliotheek bezoeken."
- Betekenis: Er moet een test zijn die deze specifieke route neemt.
- Resultaat: Dit is makkelijk op te lossen voor computers. Ze kunnen snel een route vinden die aan deze eis voldoet.
NEGATIVE (De "Verboden-Zone"):
- Regel: "Als je de kelder hebt bezocht, mag je nooit de zolder bezoeken."
- Betekenis: Geen enkele test mag deze combinatie bevatten.
- Resultaat: Dit is extreem moeilijk (NP-compleet). Het is alsof je een pad moet vinden dat alles dekt, maar nooit een bepaald stukje raakt. Het is als een puzzel waarbij je elke steen moet leggen, behalve die ene rode steen, en je moet precies weten welke combinaties dat mogelijk maken.
ONCE (De "Eén-Keer-Regel"):
- Regel: "De combinatie 'kelder + zolder' mag in het hele hele testpakket maar één keer voorkomen."
- Betekenis: Het is te duur of te zeldzaam om dit vaker te testen.
- Resultaat: Ook dit is extreem moeilijk. Je moet precies de juiste balans vinden tussen het dekken van alles en het niet overschrijden van die ene limiet.
MAX ONCE (De "Maximaal-Eén-Regel"):
- Regel: "De combinatie 'kelder + zolder' mag maximaal één keer voorkomen (of zelfs nul keer)."
- Resultaat: Net als bij ONCE is dit extreem moeilijk.
ALWAYS (De "Altijd-Volgende-Regel"):
- Regel: "Als je de kelder binnenkomt, moet je altijd later ook de zolder bezoeken in diezelfde test."
- Betekenis: Je kunt de kelder niet verlaten zonder de zolder te zien.
- Resultaat: Ook dit is extreem moeilijk.

De Grote Ontdekking: Waarom is dit zo lastig?

De auteurs hebben bewezen dat voor de meeste van deze regels (NEGATIVE, ONCE, MAX ONCE, ALWAYS), het vinden van een perfecte set tests wiskundig onmogelijk is om snel op te lossen voor grote systemen.

De Analogie: Stel je voor dat je een enorme doolhof moet afleggen met een team van renners. Je wilt dat elke muur in het doolhof wordt aangeraakt. Maar je hebt ook regels: "Renners A en B mogen nooit samen zijn", of "Renners A en B mogen maar één keer samen zijn".
Hoe meer renners en hoe groter het doolhof, hoe meer combinaties er zijn om te controleren. Voor computers wordt dit een "combinatorische explosie". Het is alsof je elke mogelijke combinatie van sleutels moet proberen om een slot te openen, en het aantal combinaties groeit exponentieel.

De Uitzondering:
Alleen bij de POSITIVE regels (waar je gewoon moet gaan) is het probleem oplosbaar in een redelijke tijd.

De Slimme Oplossing voor de "Verboden-Zone"

Hoewel het probleem voor de NEGATIVE regels (verboden combinaties) in het algemeen onoplosbaar is voor grote systemen, hebben de auteurs een slimme truc bedacht.

Ze zeggen: "Als het aantal regels (beperkingen) klein is, kunnen we het toch oplossen."

Analogie: Als je in een stad met 100 straten maar 2 of 3 specifieke verboden routes hebt, kun je die wel vinden. Maar als je 50 verboden routes hebt, wordt het weer onmogelijk.
Ze hebben een algoritme gemaakt dat werkt als je het aantal regels klein houdt. Dit noemen ze FPT (Fixed-Parameter Tractable). Het is alsof je een speciale bril opzet die alleen de regels ziet; als er maar een paar zijn, kun je de weg vinden, zelfs in een groot doolhof.

Conclusie in Eén Zin

Dit onderzoek laat zien dat het toevoegen van realistische regels aan softwaretesten (zoals "dit mag niet" of "dit moet altijd") de taak voor computers vaak onmogelijk maakt om snel op te lossen, tenzij je maar heel weinig regels hebt. Het is een waarschuwing voor softwareontwikkelaars: wees voorzichtig met het toevoegen van te veel complexe beperkingen, want dan wordt het vinden van goede tests een wiskundige nachtmerrie.

Titel: Berekeningscomplexiteit van het Edge Coverage-probleem voor Geconstrueerde Control Flow Graphs

Auteurs: Jakub Ruszil, Artur Polański, Adam Roman, en Jakub Zelek (Jagiellonian Universiteit, Polen).

1. Probleemstelling

Het artikel onderzoekt de complexiteit van het genereren van testsets voor Edge Coverage (EC) (randdekking) in Control Flow Graphs (CFG) die zijn uitgebreid met expliciete beperkingen (constraints).

Achtergrond: Witte-doos testing (white-box testing) gebruikt vaak CFG's om testgevallen te ontwerpen. Echter, standaard CFG's lijden aan een "semantische kloof" (semantic gap): ze staan paden toe die in de praktijk onmogelijk uitvoerbaar zijn, of ze negeren domeinspecifieke regels (zoals verplichte volgorde of resource-limieten).
Het probleem: Hoe beïnvloeden extra beperkingen tussen knopen (vertices) de haalbaarheid en de computatiecomplexiteit van het vinden van een testset die:
1. Alle randen (edges) van de CFG dekt (Edge Coverage).
2. Een specifieke set van beperkingen respecteert.
Doel: Het theoretisch analyseren of dit probleem in polynomiale tijd (P) oplosbaar is of NP-compleet (NPC), en het onderzoeken van parameterisatie (FPT).

2. Methodologie en Definities

De auteurs definiëren een geconstrueerde Control Flow Graph (cCFG) als een 6-tupel $G = (V, E, s, t, C, X)$ , waarbij $C$ een set beperkingen is en $X$ het type beperking bepaalt.

Er worden vijf types beperkingen onderzocht:

POSITIVE ( $C^+$ ): Er moet minstens één testpad zijn waarbij knoop $x$ voorkomt vóór knoop $y$ .
NEGATIVE ( $C^-$ ): Er mag geen testpad zijn waarbij $x$ voorkomt vóór $y$ .
ONCE ( $C^1$ ): Er moet exact één testpad zijn met $x$ vóór $y$ , en in dat pad mag $x$ slechts één keer voorkomen vóór $y$ (en $y$ slechts één keer na $x$ ).
MAX-ONCE ( $C^{\le 1}$ ): Er mag in maximaal één testpad voorkomen dat $x$ vóór $y$ komt.
ALWAYS ( $C^=$ ): Als $x$ voorkomt in een testpad, dan moet $y$ altijd later in datzelfde pad voorkomen.

Het centrale vraagstuk is de beslissingsprobleem: Bestaat er een toelaatbare testset (die aan de beperkingen voldoet) die alle randen van de grafiek dekt?

3. Belangrijkste Resultaten en Complexiteit

De auteurs hebben de complexiteit voor elk van de vijf beperkingstypen bepaald door middel van polynoomreducties vanuit varianten van het 3-SAT-probleem.

Beperkingstype	Complexiteit	Toelichting
POSITIVE ( $C^+$ )	Polynoom (P)	Het probleem is oplosbaar in polynoomtijd. Men kan een standaard EC-oplossing nemen en voor elke beperking een extra pad toevoegen dat $x$ en $y$ verbindt, mits $x$ bereikbaar is vanuit de start en $y$ naar de eindknop.
NEGATIVE ( $C^-$ )	NP-compleet	Het probleem is NP-compleet, zelfs voor acyclische grafieken. Bewijs via reductie van 3-SAT waarbij "verboden" overgangen (rode vs. blauwe knopen) de logische waarheidswaarden simuleren.
MAX-ONCE ( $C^{\le 1}$ )	NP-compleet	NP-compleet. Bewijs via reductie van 3-SAT waarbij de beperking dat een combinatie slechts één keer mag voorkomen, de zoekruimte beperkt tot een geldige satisfactie.
ONCE ( $C^1$ )	NP-compleet	NP-compleet. Vergelijkbaar met MAX-ONCE, maar vereist dat de combinatie exact één keer voorkomt. Bewijs gebruikt een variant van 3-SAT waarbij literalen uniek zijn.
ALWAYS ( $C^=$ )	NP-compleet	NP-compleet, zelfs voor acyclische grafieken. Bewijs via reductie van POSITIVE 1-in-3 SAT (waarbij elke clausule precies één waar literal moet hebben).

Conclusie over complexiteit: Met uitzondering van POSITIVE-constraints, is het vinden van een edge-covering testset voor alle andere typen beperkingen NP-compleet. Dit betekent dat er waarschijnlijk geen efficiënt algoritme bestaat voor het algemene geval.

4. Fixed-Parameter Tractability (FPT)

Ondanks de NP-completheid van het NEGATIVE-probleem, tonen de auteurs aan dat het Fixed-Parameter Tractable (FPT) is met betrekking tot het aantal beperkingen ( $|C|$ ).

Algoritme: Ze presenteren een algoritme (HasEdgeCoverageWithNegative) dat werkt door te itereren over alle mogelijke "volgorde-sequenties" ( $c$ ) van de betrokken knopen in de beperkingen.
Mechanisme:
- Het algoritme definieert een "c-proper" pad: een pad dat de beperkingen respecteert door de volgorde van knopen strikt te volgen zoals gedefinieerd door de sequentie $c$ .
- Het gebruikt een hulpprocedure (FindProperPath) die in polynoomtijd bepaalt of een pad bestaat dat een specifieke rand dekt en tegelijkertijd voldoet aan de sequentie-beperkingen.
Tijdcomplexiteit: $f(|C|) \cdot p(|V| + |E|)$ . De exponentiële factor zit alleen in het aantal beperkingen, terwijl de grafiekgrootte polynomiaal blijft. Dit maakt het probleem praktisch oplosbaar voor systemen met een klein aantal beperkingen, zelfs als de grafiek groot is.

5. Significantie en Toekomstig Werk

Theoretische bijdrage: Dit is een van de eerste werken dat de theoretische complexiteit van constraint-based path testing formeel analyseert. Het toont aan dat het toevoegen van realistische beperkingen (zoals verboden paden of verplichte volgorde) de complexiteit van het testontwerp drastisch verhoogt.
Praktische implicatie: Testers moeten zich bewust zijn dat het automatisch genereren van testsets voor complexe scenario's (met verboden paden of strikte volgorde) computationeel zwaar kan zijn. Voor grote systemen met veel beperkingen zijn heuristieken of benaderingsalgoritmen nodig, tenzij het aantal beperkingen klein is (waarbij FPT-algoritmen bruikbaar zijn).
Toekomstig onderzoek: De auteurs suggereren dat het interessant is om te onderzoeken of FPT-algoritmen ook bestaan voor ONCE, MAX-ONCE en ALWAYS constraints. Daarnaast zou het nuttig zijn om grafieken te analyseren met gemengde typen beperkingen tegelijkertijd, wat dichter bij realistische softwaresystemen ligt.

Samenvatting van de Bijdrage

Het artikel levert een fundamentele classificatie van de complexiteit van edge coverage onder beperkingen. Het bewijst dat terwijl positieve eisen eenvoudig zijn, negatieve en kwantitatieve beperkingen het probleem NP-compleet maken. Echter, door het aantal beperkingen als parameter te gebruiken, kan het negatieve geval efficiënt worden opgelost, wat een waardevolle inzage biedt voor tool-ontwikkelaars in de softwaretesting.