13.5 Bounds-ellenőrzött parser és állapotgép

Egy parser helyessége nem csupán azt jelenti, hogy felismeri a megfelelő formátumot. Azt is garantálnia kell, hogy a csonka, hibás vagy szándékosan támadó bemenet feldolgozása során nem olvas objektumhatáron túl, nem számol túlcsorduló méretekkel, és nem ad vissza már érvénytelen tárolóra mutató eredményt.

A Byte order és biztonságos szerializálás, valamint a Memóriamásolás, összehasonlítás és byte view szabályaira építve egy egyszerű bináris formátumot dolgozunk fel: két, big-endian sorrendű oktett adja meg az utánuk következő payload hosszát. A payload tetszőleges bináris adat, tehát nullkaraktert is tartalmazhat. A parser alkalmazási korlátja 4096 oktett.

13.5.1 Cursor, tartomány és hibaszerződés

A cursor a következő feldolgozandó pozíció. Pointeres reprezentációban három értéket tartunk nyilván:

• begin: a teljes bemeneti tartomány kezdete;
• cur: a következő olvasás helye;
• end: a tartomány utáni, már nem dereferálható pozíció.

ISO C17-szabály: a pointerkivonás csak megfelelő közös tömbobjektumon belül, az egy-past pozíciót is megengedve értelmezett; az eredménynek ábrázolhatónak kell lennie ptrdiff_t típusban. A parser előfeltétele ezért:

$$0 \leq \text{cur}-\text{begin} \leq \text{end}-\text{begin} \leq \text{PTRDIFF\_MAX}.$$

Ekkor a hátralévő elemszám és az aktuális offset:

$$R=\text{end}-\text{cur}, \qquad O=\text{cur}-\text{begin}.$$

Mivel unsigned char elemekkel dolgozunk, ezek C bájtban értendők. A példában külön előfeltétel a CHAR_BIT == 8, így egy C bájt egy oktett.

Az invariáns nem igazolható tetszőleges pointerek összehasonlításával: már az összehasonlítás vagy kivonás is megsértheti a nyelvi szabályokat. A helyes tartomány létrehozása a hívó kötelessége. Üres bemenethez is használunk egy élő objektumból képzett pointert; nem vonunk ki két null pointert.

A parser egy kötelező következő rekordot keres, és az alábbi szerződést vállalja:

Ez tranzakciós partial-result policy: hibánál nincs részleges payload-eredmény. A hibaadat saját enumot és offsetet tartalmaz, nem a bemenetből kölcsönzött hibaüzenetet.

13.5.2 Kidolgozott C17-parser

Az alábbi teljes fájl neve parser.c. A c, out és error érvényes, egymástól és a bemenettől elkülönülő objektumokra mutasson. A bemenet a hívás alatt nem változhat. Tulajdonosa a hívó; a parser nem allokál és nem szabadít fel.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <limits.h>

_Static_assert(CHAR_BIT == 8, "The wire format requires 8-bit bytes.");

enum { MAX_PAYLOAD = 4096 };

enum parse_code {
    P_OK,
    P_NEED_MORE,
    P_TRUNCATED,
    P_LIMIT
};

struct cursor {
    const unsigned char *begin;
    const unsigned char *cur;
    const unsigned char *end;
};

struct token_view {
    const unsigned char *data;
    size_t size;
};

struct parse_error {
    enum parse_code code;
    size_t offset;
};

static enum parse_code report(struct parse_error *error,
                              enum parse_code code,
                              size_t offset)
{
    *error = (struct parse_error){code, offset};
    return code;
}

enum parse_code parse_one(struct cursor *c, bool final,
                          struct token_view *out,
                          struct parse_error *error)
{
    const size_t remaining = (size_t)(c->end - c->cur);
    const size_t start = (size_t)(c->cur - c->begin);
    const enum parse_code incomplete =
        final ? P_TRUNCATED : P_NEED_MORE;

    if (remaining < 2) {
        return report(error, incomplete, start + remaining);
    }

    const size_t length =
        (size_t)c->cur[0] * 256u + (size_t)c->cur[1];

    if (length > MAX_PAYLOAD) {
        return report(error, P_LIMIT, start);
    }

    if (length > remaining - 2) {
        return report(error, incomplete, start + remaining);
    }

    const unsigned char *payload = c->cur + 2;

    *out = (struct token_view){payload, length};
    c->cur = payload + length;
    return report(error, P_OK, (size_t)(c->cur - c->begin));
}

#ifndef PARSER_FUZZ
int main(void)
{
    const unsigned char input[] = {
        0x00, 0x03, 0x41, 0x00, 0xff
    };

    struct cursor c = {input, input, input + sizeof input};
    struct token_view out = {NULL, 0};
    struct parse_error error = {P_OK, 0};

    const enum parse_code result =
        parse_one(&c, true, &out, &error);

    assert(result == P_OK);
    assert(out.size == 3);
    assert(out.data[0] == 0x41);
    assert(out.data[1] == 0x00);
    assert(out.data[2] == 0xff);
    assert(c.cur == c.end);
    assert(error.offset == sizeof input);
    return 0;
}
#endif

Fordítási profil: ISO C17; Linux x86-64, System V ABI, LP64, 8 bites C bájt. Konkrét laborválasztásként GCC 14.2.0 vagy Clang 19.1.7 és glibc 2.39 használható; a telepített párosítást külön rögzíteni kell. A parancsok nem jelentenek dokumentált fordítási vagy futtatási eredményt.

gcc-14 -std=c17 -Wall -Wextra -Wpedantic -Wconversion \
    -O1 -g -fsanitize=address,undefined \
    parser.c -o parser-check

13.5.2.1 Miért ilyen sorrendben ellenőrzünk?

A hosszmező legnagyobb értéke:

$$255\cdot256+255=65535.$$

Ez a választott profil size_t típusában ábrázolható. Hosszabb, például 64 bites wire-hossz esetén külön ellenőrizni kellene a size_t tartományába illeszkedést; a szűkítő konverzió nem helyettesíti ezt.

A payload ellenőrzésénél nem a 2 + length > remaining összeget képezzük, hanem előbb igazoljuk, hogy remaining >= 2, majd kivonunk:

$$\text{length}\leq \text{remaining}-2.$$

Bizonyításvázlat: az első ellenőrzés biztosítja a két fejlécbájt olvashatóságát és a kivonás alulcsordulás-mentességét. A második biztosítja, hogy a teljes payload a tartományon belül van. Csak ezek után képezzük a payload végét. A hibapozícióként használt start + remaining pontosan a teljes tartomány hossza, ezért az előfeltételek mellett nem csordul túl.

A golden case deklarált hossza három. Payload-offsetje kettő, következő cursor-offsetje öt. Ha az utolsó oktett hiányzik, az eredmény végleges bemenetnél P_TRUNCATED, az offset pedig négy: itt kellett volna folytatódnia az adatnak. A P_LIMIT ezzel szemben a hibás hosszmező kezdetére mutat.

13.5.3 View, saját másolat vagy arena?

A token_view csak pointert és hosszt másol. Nem másolja át a payloadot, és nem veszi át annak tulajdonlását.

A bemenet felülírása nem feltétlenül szünteti meg a pointer nyelvi érvényességét, de megváltoztatja a view által megfigyelt adatot. Emiatt egy újrahasznosított fogadóbufferből származó view-t nem szabad változatlan eredményként tárolni.

Saját, nullterminált sztringhez előbb ellenőrizni kell, hogy az $n+1$ tárolóméret ábrázolható, majd kezelni az allokáció hibáját. A másolás és a lezáró nullkarakter elhelyezése után is meg kell őrizni a hosszt, ha beágyazott nullkarakter megengedett. Bináris payloadhoz a strlen nem használható.

Sok, közös élettartamú tokenhez az Arena, pool és region lifetime modellje megfelelő. Az arena azonban csak a ténylegesen bemásolt adatot birtokolja: egy benne tárolt view továbbra is függhet egy külső inputbuffertől. Hash táblába helyezett tokenkulcsnál ugyanezt az ownership-döntést kell meghozni; lásd Hash table, comparator és ownership.

13.5.4 Streaming feldolgozás mint állapotgép

A parse_one teljes, összefüggő tartományt vizsgál. P_NEED_MORE után a hívónak meg kell őriznie a teljes feldolgozatlan prefixet, és kibővített tartománnyal újrapróbálkoznia. Újraallokálás után a cursor pointereit megőrzött offsetekből, az új bázisból kell újraképezni.

Valódi streaming parser ehelyett menet közben is elfogyaszthatja a chunkokat. Egy egyszerű megvalósítás a parserállapot saját, 4096 oktettes payload-tárolójába másol:

Nulla hossz esetén a fejléc után közvetlenül READY következik. A parser ne írja felül a kész eredményt annak átvétele előtt.

A mintabemenet három chunkban:

1. 00: egy fejlécoktett, további adat szükséges;
2. 03 41: ismert a háromoktettes hossz, egy payload-oktett megvan;
3. 00 ff: elkészül a rekord.

Másoláskor a mennyiség:

$$k=\min(\text{chunk remaining},\ \text{length}-\text{used}).$$

Az állapot saját tárolójára mutató eredmény-view legfeljebb a következő felülírásig/resetig, illetve az állapotobjektum életének végéig használható. A chunk kölcsönzött tárolója viszont a feldolgozóhívás után elengedhető, ha minden szükséges adatot átmásoltunk.

A stream API külön adja vissza az elfogyasztott chunkhosszt. Itt a NEED_MORE nem jelenti azt, hogy semmi sem fogyott el. Végleges bemenetnél a részleges fejléc vagy payload csonka rekord; két rekord között az üres HEADER állapot szabályos streamvég lehet. Az abszolút offset növelése előtt ellenőrizni kell:

$$k\leq\text{SIZE\_MAX}-\text{total}.$$

13.5.4.1 Mélység- és erőforráskorlátok

A példanyelv lapos, így nincs bemenetfüggő rekurzió. Egymásba ágyazható konfigurációs nyelvnél azonban minden rekurzív leszállás előtt ellenőrizni kell a mélységkorlátot. Ha depth >= max_depth, a parser adjon külön mélységhibát, ne hívja meg önmagát.

A mélységkorlát nem helyettesíti a tokenek számára vagy az összes másolt adatra vonatkozó keretet. Az állapotgép ciklusa pedig vagy fogyasszon inputot, vagy váltson előrehaladást biztosító állapotba, vagy térjen vissza. Különben UB nélkül is létrejöhet szolgáltatásmegtagadást okozó végtelen ciklus.

13.5.5 Golden case, round-trip és fuzz harness

A golden case ismert wire-bájtokhoz ismert eredményt rendel. A round-trip tulajdonság azt ellenőrzi, hogy egy érvényes rekord szerializálása, majd visszaolvasása megőrzi a hosszt és a payloadot. Önmagában ez kevés: az encoder és a decoder ugyanazt a byte-order hibát is tartalmazhatja.

Az alábbi részt a parser.c végéhez lehet hozzáadni. A bemenetet a fuzzoló biztosítja, a harness csak a hívás idejére kölcsönzi; sem pointert, sem view-t nem őriz meg.

#ifdef PARSER_FUZZ
int LLVMFuzzerTestOneInput(const unsigned char *data, size_t size)
{
    unsigned char empty = 0;

    if (size > (size_t)PTRDIFF_MAX) {
        return 0;
    }

    const unsigned char *base = size == 0 ? &empty : data;

    for (int final = 0; final < 2; ++final) {
        struct cursor c = {base, base, base + size};
        struct token_view out = {NULL, SIZE_MAX};
        struct parse_error error = {P_OK, 0};

        const enum parse_code result =
            parse_one(&c, final != 0, &out, &error);

        assert(error.code == result);
        assert(error.offset <= size);

        if (result == P_OK) {
            assert(size >= 2);
            assert(out.size <= MAX_PAYLOAD);
            assert(out.size <= size - 2);
            assert(out.data == base + 2);
            assert(c.cur == out.data + out.size);
        } else {
            assert(c.cur == base);
            assert(out.data == NULL);
            assert(out.size == SIZE_MAX);
        }
    }

    return 0;
}
#endif

Eszközspecifikus profil: Clang 19.1.7, elérhető libFuzzer- és sanitizer-runtime-mal. Ezek nem ISO C szolgáltatások.

clang-19 -std=c17 -DPARSER_FUZZ \
    -Wall -Wextra -Wpedantic -O1 -g \
    -fsanitize=fuzzer,address,undefined \
    parser.c -o parser-fuzz

A hibás input itt normál visszatérési értéket eredményez; az assertion megsértése parser- vagy harnesshibát jelez. A fuzzolás és a sanitizerek hibakereső eszközök, nem teljes helyességbizonyítások.

13.5.6 Gyakori hibák

• Bounds-ellenőrzés előtti dereferencia: már a hosszmező olvasása is kilóghat. Előbb a fejléc méretét ellenőrizzük.
• cur + length képzése az ellenőrzéshez: az érvénytelen pointerképzés megelőzheti az összehasonlítást. Maradékhosszal számolunk.
• Minden hiányos input végleges hibának minősítése: streaming esetben külön kell választani a várakozást és a csonka streamvéget.
• Részben kitöltött eredmény hibánál: a hívó könnyen kész rekordnak tekinti. A publikálás csak az összes ellenőrzés után történjen.
• View megtartása buffer-újrahasznosítás után: másolás vagy dokumentált owner-élettartam szükséges.

13.5.7 Feladatok

1. Magyarázó: Mi az eredmény a 00 03 41 bemenetre final == false, illetve final == true mellett? Hol van a hibaoffset?
2. Kódolási: Tervezz parse_exact wrappert, amely pontosan egy rekordot fogad el, és elutasítja a trailing adatot. Hibánál maradjon változatlan a kimenet.
3. Diagnosztikai: A streaming parser payload-view-ját egy eseménysorba tesszük, majd ugyanabban a tárolóban fogadjuk a következő rekordot. Miért romolhat el az eredmény sanitizerjelzés nélkül? Adj javítást és ellenőrzési feltételt.

13.5.8 Megoldások

13.5.8.1 Hiányos payload

Nem végleges inputnál P_NEED_MORE, véglegesnél P_TRUNCATED az eredmény. Az offset három: ott hiányzik a következő oktett. A cursor és az out változatlan.

Ellenőrzés: ugyanazt a háromoktettes tartományt mindkét final értékkel vizsgáljuk, és az állapot megőrzését is ellenőrizzük.

13.5.8.2 Pontosan egy rekord

A wrapper helyi cursorral és helyi view-val hívja a parse_one függvényt. Siker után ellenőrzi, hogy a helyi cursor elérte-e az end értéket. Ha nem, külön trailing-data hibát ad az első fölösleges oktett offsetjével. A kimenetet csak teljes siker esetén másolja ki.

Ellenőrzés: a golden case sikeres, ugyanaz egy további oktettel hibás, és a korábbi kimenet mindkét hibafajtánál érintetlen.

13.5.8.3 Újrahasznosított tároló

A pointer még élő objektumba mutathat, csak annak tartalma változott meg. Ez logikai élettartam-/ownership-hiba, ezért nem szükségszerű a sanitizerjelzés.

Javításként a sor saját payload-másolatot birtokolhat, vagy átveheti egy külön rekordtároló tulajdonlását.

Ellenőrzés: két eltérő rekord egymás utáni fogadása után az első sorbejegyzés tartalma változatlan; felszabadítása pontosan egyszer történik.

13.5.9 Összefoglaló

A biztonságos parser ellenőrzött tartományból, bizonyítottan érvényes cursorral olvas. A hosszszámítás megelőzi a pointerléptetést, a hibaoffset jelentése rögzített, és a részleges eredmény kezelése explicit. Streaming esetben külön szerződés szükséges a fogyasztásra, az állapotra és a tároló újrahasznosítására. A bounds-helyesség és a visszaadott view élettartamának helyessége két külön, egyformán szükséges garancia.