Ugrás a tartalomhoz

control flow analysis

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

control flow analysis (tsz. control flow analysises)

  1. (informatika) A control-flow analysis (CFA) egy statikus programanalízis technika, amely azt vizsgálja, hogy a program futása során milyen vezérlésútvonalak lehetségesek. Lényegében a CFA próbálja előrejelezni, hogyan fut a program, milyen sorrendben hívódnak meg függvények, utasítások, milyen esetekben melyik ág teljesülhet.

A CFA nem az adatokat, hanem a végrehajtási struktúrát elemzi – szemben például a data-flow analysis-szel, amely az értékek mozgására koncentrál.


🎯 Célja

  • Megállapítani, milyen kódrészek hajtódhatnak végre egy adott programfutás során.
  • Feltérképezni a lehetséges végrehajtási útvonalakat – beleértve az elágazásokat, ciklusokat, függvényhívásokat.
  • Optimalizálás, biztonsági elemzés, holtpontdetektálás, és verifikáció támogatása.


📘 Kulcsfogalmak

✅ Control-Flow Graph (CFG)

A CFA az elemzést általában egy vezérlésáramlási gráfon végzi:

  • Csomópontok: utasítások vagy blokk-csoportok (basic block-ok).
  • Élek: lehetséges vezérlésátmenetek (pl. ha if, goto, while).

A CFA CFG-n történő vizsgálat.


⚙️ Milyen kérdésekre válaszol?

  • Elérhető-e egy adott utasítás?
  • Hányféleképp hívható meg egy függvény?
  • Hány példányban hajtódhat végre egy ciklus?
  • Elágazásoknál mely ágak futtathatók?
  • Lehetséges-e nem kívánt végrehajtás (pl. sosem elérhető, vagy minden esetben elérhető kód)?


📈 Működési lépések

1. CFG létrehozása

Lépésenként építjük fel a vezérlésáramlási gráfot a program kódjából.

2. Elérhetőségi analízis (Reachability)

Megállapítjuk, mely csomópontok érhetők el a kezdőpontból.

3. Ágelemzés

Melyik feltétel hogyan befolyásolja az útvonalakat?

4. Útvonalanalízis

Hányféle útvonalon érhetünk el egy utasítást?


🧩 Alapvető típusa: Call Graph + CFA

A Call Graph egy különleges CFG, ahol:

  • Csomópontok = függvények
  • Élek = lehetséges függvényhívások

A Control-Flow Analysis célja gyakran ennek pontos meghatározása. Különösen fontos funkcionális vagy dinamikus nyelveknél (pl. JavaScript, Scheme), ahol függvényhívások futás közben dőlnek el.


🔢 CFA változatai (λ-kalkulusban és funkcionális nyelvekben)

0-CFA (nulladik rendű):

  • A legegyszerűbb CFA.
  • Kontextusfüggetlen: nem különböztet meg hívási helyeket.
  • Durva közelítés, de gyors.

k-CFA:

  • Kontextusérzékeny CFA.
  • k korábbi hívási kontextust is figyelembe vesz.
  • K pontosabb, de számítási igény nő.

m-Calling Context:

  • m hosszúságú veremkivágás a hívásláncból.
  • Több útvonalat tud megkülönböztetni.


🧠 Miért nehéz CFA?

  • Dinamikus diszpécser: Olyan függvényhívások, amelyek csak futásidőben dőlnek el (virtual, function pointers, eval, lambda, stb.).
  • Rekurzió: Visszacsatolásokat okoz a gráfban.
  • Feltételek és ciklusok: exponenciálisan növelhetik a lehetséges útvonalakat.


💡 Miért hasznos?

1. Optimalizálás

  • Mely ágakat lehet kihagyni?
  • Ciklusátalakítás (loop unrolling, fusion)
  • Dead code elimination

2. Biztonság

  • Elérhető-e veszélyes API egy adott bemenettel?
  • Vannak-e kódágak, amik mindig vagy soha nem futnak?

3. Funkcionális nyelvek elemzése

  • lambda kifejezések hol hívhatók?
  • Mit tudunk mondani az értékek áramlásáról a hívások alapján?

4. Verifikáció és model checking

  • Egy hibaútvonal végrehajtható?
  • Egy állapot elérhető bizonyos bemenetekkel?


🛠️ Eszközök és keretrendszerek

  • LLVM: CFG generálás, analízis, opt -dot-cfg
  • Soot (Java): k-CFA, call graph generálás
  • Frama-C: formális ellenőrzés C-ben
  • TypeScript Analyzer, Flow, Facebook Infer
  • SPARTA / WALA (Java analysis)


📌 Példa – egyszerű if-else

1: if (x > 0)
2:     y = 1;
3: else
4:     y = 2;
5: z = y + 1;

CFG:

[1]
 / \
[2] [4]
 \ /
 [5]

CFA:

  • y = 1 és y = 2 is lehetséges útvonal.
  • A z = y + 1 utasítás előtti értéke y-nak nem egyértelmű.


TL;DR

A control-flow analysis (CFA) egy statikus elemzési módszer, amely feltérképezi, hogyan haladhat a vezérlés a programban. Segít meghatározni, hogy milyen utasítások, függvények, ágak érhetők el, milyen sorrendben hajtódhatnak végre. Központi szerepe van optimalizálásban, hibadetektálásban, biztonsági auditokban, és a függvényhívások elemzésében – különösen dinamikusan típusos vagy funkcionális nyelvek esetén.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=control_flow_analysis&oldid=3504447”