control-flow graph

control-flow graph (tsz. control-flow graphs)

1. (informatika) A Control-Flow Graph (CFG) egy gráfelméleti modell, amely egy program lehetséges vezérlésútvonalait írja le. Az ilyen gráf statikus elemzések (pl. data-flow analysis, optimizáció, hibadetektálás, biztonsági vizsgálatok) alapja, és központi szerepet játszik fordítóprogramokban, elemzőeszközökben, valamint a formális verifikációban.

A vezérlésáramlási gráf egy irányított gráf, amelyben:

• Csomópontok (node): a program utasításai, basic blockjai, vagy utasításcsoportok.
• Élek (edge): lehetséges vezérlésátmenetek (pl. egy utasítás után mi hajtódhat végre).

A CFG nem az értékekkel, hanem a végrehajtás sorrendjével foglalkozik.

Egy basic block egy olyan utasítássorozat, amely:

• egyetlen belépési ponttal rendelkezik (csak az elején lehet belépni),
• egyetlen kilépési ponttal rendelkezik (csak a végén lehet kilépni),
• nem tartalmaz elágazást a blokkon belül.

Ez a CFG építőköve.

Példa:

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

Itt a basic block-ok lehetnek:

• B1: x = 0; y = 1;
• B2: if (a > b)
• B3: x = x + 1;
• B4: y = y + 1;

1: int x = 0;
2: if (a > 0)
3:     x = 1;
4: else
5:     x = -1;
6: return x;

CFG:

  
   |
  
  / \
 
  \ /
  

• Az él azt mutatja, hogy milyen irányba léphet tovább a vezérlés.
• A 2. sor egy elágazási pont (branch).

A data-flow információk (pl. elérhető definíciók, konstansok) IN/OUT halmazként tárolhatók minden csomópontnál.

Fordítók CFG-t használnak pl.:

• halott kód eltávolításához,
• loop unrolling,
• inlineolás,
• jump threading,
• basic block átrendezéshez.

Pl. unreachable kód, végtelen ciklusok, nem inicializált változók.

• Lehetséges futási útvonalak vizsgálata (taint analysis).
• Statikus sebezhetőségvizsgálat.

• Folytonos (fall-through): nincs explicit goto, if, return.
• Feltételes elágazás (conditional branch): if, switch.
• Ugrás (jump/goto): pl. ciklus vagy goto.

• A CFG-nek egy belépési pontja van (általában az első utasítás).
• Lehet több kilépési pontja (pl. return, exit, throw).

Ciklusok felismerhetők, ha egy útvonal visszavezeti a vezérlést egy korábbi blokkhoz.

Példa:

while (x < 10) {
    x++;
}

A CFG-ben ez egy önmagába visszacsatolt él.

• LLVM: opt -dot-cfg opcióval .dot fájlokat generálhat.
• GCC: -fdump-tree-cfg opció.
• Clang Static Analyzer
• Soot: Java CFG + data-flow analízishez.
• Frama-C: C programok CFG vizualizációja és verifikációja.

A CFG kibővített változata, amely adat- és vezérlésfüggéseket is tartalmaz.

Egy blokk B dominál egy másikat, ha minden úton B-hez el kell haladni rajta. Ez hasznos strukturált ciklusok, if-else blokkok felismeréséhez.

• Goto utasítás: nehézzé teszi a CFG olvashatóságát.
• Függvényhívások: interprocedurális CFG nehezebben kezelhető.
• Kivételkezelés (try-catch): nem lineáris vezérlés-átmeneteket okozhat.

A Control-Flow Graph (CFG) egy irányított gráf, amely megmutatja, hogyan haladhat a vezérlés egy programon belül. Csomópontjai utasításblokkok, élei pedig végrehajtási lehetőségek. A CFG kulcsfontosságú a fordítókban, statikus elemzőkben, és a verifikációban – alapul szolgál például az adatfolyam-analízishez, optimalizálásokhoz és biztonsági auditokhoz.

• control-flow graph - Szótár.net (en-hu)
• control-flow graph - Sztaki (en-hu)
• control-flow graph - Merriam–Webster
• control-flow graph - Cambridge
• control-flow graph - WordNet
• control-flow graph - Яндекс (en-ru)
• control-flow graph - Google (en-hu)
• control-flow graph - Wikidata
• control-flow graph - Wikipédia (angol)