Detect a stack canary pattern in a memory snapshot

Overview

Security objective. The asset being protected is a function's saved return address on the stack. The threat is a stack-based buffer overflow: attacker-controlled input overruns a local buffer and overwrites the return address, redirecting execution. The stack canary is the defensive control that detects this tampering before the function returns. In this lesson you build a detector that recognises the canary's byte pattern inside a memory snapshot — a read-only forensics/QA task, not an exploit.

A stack canary (also called a stack cookie) is a random machine word the compiler places between a function's local variables and its saved return address. On entry the value is loaded from a per-process secret; on exit the epilogue compares the on-stack copy against that secret. If a buffer overflow ran past the locals, it had to march through the canary first — so a mismatch means "the frame was corrupted, abort now" instead of returning into attacker-controlled memory.

This lesson builds directly on your pointers prereq — you walk a const uint8_t * snapshot with pointer arithmetic and bounds math — and on byte-patterns, because a canary is recognised purely by its byte signature: low byte 0x00, and at least one of the upper seven bytes non-zero. You are not smashing a stack; you are reading a captured frame and classifying 8-byte slots.

Where you meet this in practice: reverse-engineering a crash dump, writing a memory-forensics check, or a defensive QA tool that confirms a hardened binary really did place canaries where you expect. It connects forward to libfuzzer-entrypoint, where the same defensive mindset — detect corruption early — drives how you write fuzz targets.

Why it matters

In authorized professional work, recognising a canary's shape is a foundational reversing and hardening skill.

• Build verification / hardening audits. Security engineers confirm that release binaries were actually compiled with -fstack-protector-strong. Being able to spot the canary word in a frame — or its absence — turns "we think it's on" into evidence.
• Crash-dump triage. When a service crashes with *** stack smashing detected ***, an analyst inspects the core dump. Knowing exactly where the canary sits and what its byte shape is lets you tell an accidental corruption from a deliberate overflow attempt.
• Detection engineering. SSP aborts (__stack_chk_fail) are a high-signal event. Understanding the canary explains why that abort fired and how to wire it into logging and alerting.
• Honest scoping. Knowing the canary is a detection control — not a prevention of all memory bugs — keeps risk assessments accurate. It stops a bug (return-address overwrite via linear overflow) but does not stop, say, a targeted write past the canary or a heap overflow.

All of this is defensive: you read snapshots you are authorized to inspect and report what you find.

Core concepts

1. The stack frame and the asset at risk

Definition. A stack frame is the region a function uses for its locals, saved registers, and its saved return address — the address execution jumps back to when the function returns.

Plain explanation. On x86_64 the stack grows downward (toward lower addresses), but a char buf[N] is written upward (toward higher addresses). So an overflow of buf overruns toward the saved return address. If nothing guards that path, overwriting the return address hijacks control flow.

When/when-not. The return address is the classic asset. Canaries protect it and saved registers; they do not protect arbitrary heap objects or guard against overwrites that skip the canary.

Pitfall. Assuming "overflow toward higher addresses" means the frame layout is intuitive — compilers reorder locals (arrays are often placed closest to the canary precisely so an array overflow trips it first).

2. The stack canary (stack cookie)

Definition. A random machine word placed by the compiler between the locals and the saved return address, checked in the function epilogue.

How it works.

1. Function prologue: load the secret canary from thread-local storage (on glibc x86_64, %fs:0x28) and store it just below the saved return address.
2. Function body runs; a buffer overflow that reaches the return address must overwrite the canary on the way.
3. Function epilogue: reload the on-stack copy, compare to the TLS secret. Equal → return normally. Not equal → call __stack_chk_fail, which prints *** stack smashing detected *** and aborts (SIGABRT).

When/when-not. Emitted when you compile with -fstack-protector, -fstack-protector-strong (common default on modern distros), or -fstack-protector-all. Not present with -fno-stack-protector, and -fstack-protector (plain) only guards functions with certain risky locals.

Pitfall. Thinking a canary prevents overflows. It does not — the overflow still happens; the canary makes it detectable at return so the process aborts before jumping to a corrupted address.

3. The terminator (null-low-byte) canary

Definition. A canary whose least-significant byte is 0x00 so that C string functions stop before cleanly copying a forged canary through.

Plain explanation. strcpy/gets-style writes copy until a \0. If the canary's low byte is a null, an attacker feeding a string cannot include that null mid-string without terminating their own copy — so they cannot rebuild the exact canary value past it. glibc's x86_64 canary uses this: low byte 0x00, upper 7 bytes random.

When/when-not. This is the signature you detect. Note it is a heuristic: other data can incidentally have a null low byte, so a match is a candidate, not proof.

Pitfall. Treating an all-zero word as a canary. A real canary has entropy in its upper 7 bytes; a fully null slot is just zeroed memory. Your detector must reject it.

Threat model

Asset:            saved return address in a function's stack frame
Control:          stack canary (random word) between locals and return addr
Entry point:      untrusted input written into a local buffer (e.g. read()/strcpy)
Trust boundary:   [ untrusted input ]  -->|  local buffer  | canary | saved RIP
                                         ^ boundary crossed by a linear overflow

Attack path (what the canary detects):
  input -> overruns buf -> overwrites canary -> overwrites saved RIP
                              |
                              +-- epilogue compares canary vs %fs:0x28
                                    mismatch -> __stack_chk_fail -> abort

This lesson's tool (defensive, read-only):
  captured frame snapshot (bytes) -> detector -> "canary-shaped slot at offset X?"
  No writing, no execution, no tampering.

Knowledge check.

1. What asset does the stack canary protect, and where is the trust boundary in the frame layout above?
2. What insecure assumption does a linear stack overflow rely on that the canary breaks?
3. Which log line / signal tells you a canary check failed at runtime, and why is inspecting the snapshot only appropriate on a system you are authorized to analyze?

Syntax notes

The detector treats the snapshot as a flat byte array and steps one 8-byte word at a time. The key structural rules:

#include <stdint.h>   /* uint8_t, fixed-width bytes            */
#include <stddef.h>   /* size_t, NULL                          */

/* frame : read-only snapshot bytes (we never modify them)
 * n     : length in bytes; MUST be a multiple of 8 (word-aligned)
 * return: 1 = canary-shaped slot found, 0 = none, -1 = bad input */
int has_canary_pattern(const uint8_t *frame, size_t n);

Annotated core of one slot check (little-endian layout, low byte first):

const uint8_t *slot = frame + i;   /* i steps by 8 each loop     */
int low_zero   = (slot[0] == 0);   /* terminator byte 0x00        */
int upper_set  = 0;                /* any of bytes 1..7 non-zero? */
for (size_t k = 1; k < 8; k++)
    if (slot[k] != 0) { upper_set = 1; break; }
if (low_zero && upper_set) return 1;  /* canary shape */

Guard rails to include before the loop: if (frame == NULL || (n % 8) != 0) return -1;. Iterate with for (size_t i = 0; i + 8 <= n; i += 8) so you never read past the buffer.

Lesson

Why this matters

A stack canary is a guard value the compiler places on the stack to detect overflows.

Linux toolchains use it like this:

• A random machine word is inserted between a function's local variables and its saved return address.
• The value is checked right before the function returns.
• If it changed, the program aborts instead of returning to a corrupted address.

On glibc x86_64, the canary's low byte is always 0x00. This null byte is deliberate: a naive string-write overflow stops at the first null, so it cannot copy a correct canary value through without being detected.

We are not writing a stack-smasher here. We are writing a detector. The goal is to recognise the canary's shape: a machine word whose low byte is zero, sitting in a specific frame slot.

Your job

Implement this function:

int has_canary_pattern(const uint8_t *frame, size_t n);

Return:

• 1 if any 8-byte aligned slot matches the canary signature. That means:

  • the low byte (the first byte of the slot) is 0x00, and
  • the upper 7 bytes contain at least one non-zero byte.

  In short: low byte zero, the rest random.

• 0 if no such slot exists.

• -1 if frame == NULL, or if n is not a multiple of 8.

Common mistakes

• Treating an all-zero word as a canary. The whole point is that the upper 7 bytes are random. A fully null slot is not a canary.
• Walking the frame unaligned. Stack canaries sit on a word boundary, so step exactly 8 bytes at a time.

What this is NOT

• Not a bypass. We detect the pattern; we do not tamper with it.
• Not a definitive identifier. This is a heuristic, so false positives are possible.

Code examples

Below is a complete, self-contained C11 program. It shows the naive-but-wrong shape first (so you can see the trap), then the correct detector, then tests that must REJECT decoys and ACCEPT a real canary shape.

/* recognise_stack_canary.c
 * Build: cc -std=c11 -Wall -Wextra -fstack-protector-strong \
 *           recognise_stack_canary.c -o canary_detect
 * Run:   ./canary_detect
 *
 * Read-only detector for a glibc-style stack-canary byte pattern in a
 * captured frame snapshot. It never writes to, executes, or tampers with
 * any stack. Analyze only snapshots you are authorized to inspect.
 */
#include <stdint.h>
#include <stddef.h>
#include <stdio.h>
#include <assert.h>

/* ---- (1) NAIVE / INCORRECT detector -----------------------------------
 * WARNING: intentionally flawed classifier — shown for teaching only.
 * It flags ANY word with a null low byte, so a fully zeroed slot (not a
 * canary) is a false positive, and it ignores alignment/length checks. */
static int naive_has_canary(const uint8_t *frame, size_t n) {
    for (size_t i = 0; i < n; i++)          /* wrong: byte-by-byte, unaligned */
        if (frame[i] == 0)                  /* wrong: any null passes         */
            return 1;
    return 0;
}

/* ---- (2) CORRECT detector ---------------------------------------------
 * Slot matches the canary shape iff:
 *   - byte 0 (low byte) == 0x00           (terminator byte), AND
 *   - at least one of bytes 1..7 != 0     (upper 7 bytes random).
 * Returns 1 = match found, 0 = none, -1 = invalid input. */
int has_canary_pattern(const uint8_t *frame, size_t n) {
    if (frame == NULL || (n % 8u) != 0u)    /* reject bad input safely */
        return -1;

    for (size_t i = 0; i + 8u <= n; i += 8u) {   /* aligned, in-bounds */
        const uint8_t *slot = frame + i;
        if (slot[0] != 0)                        /* low byte must be zero */
            continue;
        for (size_t k = 1; k < 8u; k++) {        /* need upper entropy   */
            if (slot[k] != 0)
                return 1;                        /* low zero + rest set  */
        }
        /* fell through: this slot was all-zero -> NOT a canary */
    }
    return 0;
}

/* ---- (3) TESTS: prove REJECT bad, ACCEPT good -------------------------- */
static void run_tests(void) {
    /* Real glibc-style canary shape: low byte 0x00, upper 7 random. */
    const uint8_t canary[8]   = {0x00, 0x2f, 0x9a, 0x71, 0xc4, 0x0d, 0xe8, 0x53};
    /* Decoy A: fully zeroed word -> must be REJECTED (not a canary). */
    const uint8_t zeros[8]    = {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
    /* Decoy B: non-null low byte -> not the terminator shape. */
    const uint8_t no_null[8]  = {0x11, 0x2f, 0x9a, 0x71, 0xc4, 0x0d, 0xe8, 0x53};
    /* A wider frame: two junk words then a canary in the third slot. */
    const uint8_t frame[24]   = {
        0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,  /* junk local #1 */
        0xde,0xad,0xbe,0xef,0x01,0x02,0x03,0x04,  /* junk local #2 */
        0x00,0x2f,0x9a,0x71,0xc4,0x0d,0xe8,0x53   /* canary slot   */
    };

    /* ACCEPT: genuine canary shape. */
    assert(has_canary_pattern(canary, sizeof canary) == 1);
    /* REJECT: all-zero decoy (this is where the naive version fails). */
    assert(has_canary_pattern(zeros, sizeof zeros) == 0);
    /* REJECT: no terminator byte. */
    assert(has_canary_pattern(no_null, sizeof no_null) == 0);
    /* ACCEPT: canary embedded later in a larger, aligned frame. */
    assert(has_canary_pattern(frame, sizeof frame) == 1);
    /* Invalid input handling. */
    assert(has_canary_pattern(NULL, 8) == -1);
    assert(has_canary_pattern(canary, 7) == -1);   /* not a multiple of 8 */

    /* Show the naive detector's false positive explicitly. */
    assert(naive_has_canary(zeros, sizeof zeros) == 1);   /* WRONG classification */
    assert(has_canary_pattern(zeros, sizeof zeros) == 0);  /* correct */

    printf("all tests passed\n");
}

int main(void) {
    run_tests();
    return 0;
}

Expected output when compiled and run:

all tests passed

What the code shows. The naive classifier passes the all-zero decoy (a false positive), while has_canary_pattern correctly rejects it because the upper bytes carry no entropy. The tests demonstrate the fix ACCEPTS a real canary shape (isolated and embedded in a larger frame) and REJECTS both decoys plus invalid input.

Line by line

Walkthrough of has_canary_pattern against the 24-byte frame:

1. frame == NULL? No. n % 8 = 24 % 8 = 0, so input is valid — we do not return -1.
2. Loop i = 0: slot = frame + 0. slot[0] = 0x11 ≠ 0 → continue. (First junk word skipped on the low-byte test alone.)
3. Loop i = 8: slot[0] = 0xde ≠ 0 → continue.
4. Loop i = 16: slot[0] = 0x00 → passes the low-byte test. Inner loop checks bytes 1..7: slot[1] = 0x2f ≠ 0 → upper_set, so we return 1.
5. Caller sees 1: a canary-shaped slot exists at offset 16.

Trace table:

Contrast with the all-zero decoy zeros: i = 0, slot[0] = 0x00 passes the low-byte test, but the inner loop finds every one of bytes 1..7 equal to 0, so it never sets upper_set and never returns 1. The loop ends and we return 0 — correctly rejecting zeroed memory. This single inner-loop distinction is what separates the correct detector from the naive one.

Common mistakes

Mistake 1 — Counting all-zero words as canaries.

• Wrong: return 1 as soon as the low byte is zero.
• Why wrong: zeroed stack memory has a null low byte too; you flag padding and uninitialized slots as canaries (false positives).
• Corrected: require the low byte to be zero and at least one upper byte non-zero.
• Recognise/prevent: add an all-zero decoy to your test suite and assert it returns 0.

Mistake 2 — Walking the frame unaligned (byte by byte).

• Wrong: for (i = 0; i < n; i++).
• Why wrong: canaries sit on 8-byte word boundaries; scanning every byte offset finds spurious "low byte zero" patterns inside unrelated data.
• Corrected: step i += 8 and treat each 8-byte slot as a unit.
• Recognise/prevent: test with a canary placed at offset 16 and junk before it; an unaligned scan will report matches at the wrong offsets.

Mistake 3 — Reading past the buffer.

• Wrong: for (i = 0; i <= n; i += 8) or dereferencing slot[7] when fewer than 8 bytes remain.
• Why wrong: out-of-bounds read — undefined behaviour, and in a security tool a potential crash on attacker-influenced input sizes.
• Corrected: guard i + 8 <= n, and reject n % 8 != 0 up front.
• Recognise/prevent: run under AddressSanitizer (-fsanitize=address) with a length that is not a multiple of 8.

Mistake 4 — Assuming endianness/byte order without stating it.

• Wrong: checking slot[7] for the terminator byte.
• Why wrong: on little-endian x86_64 the low byte is at offset 0; the terminator is slot[0], not slot[7].
• Corrected: document that the snapshot is little-endian and test the low byte at index 0.

Mistake 5 — Claiming a match proves it is a canary.

• Wrong: reporting "canary found" as fact.
• Why wrong: it is a heuristic — any word with a null low byte and non-zero upper bytes matches.
• Corrected: report it as a candidate and corroborate with frame layout / the value at %fs:0x28 in a debugger.

Debugging tips

Common errors and how to chase them:

• assert fires on the all-zero case. Your inner loop is returning 1 on zeroed memory. Print the slot bytes and confirm you only return 1 after finding a non-zero upper byte, not on the low-byte test alone.
• Detector returns 1 at a wrong offset. You are probably iterating unaligned. Print i on each match; if it is not a multiple of 8, fix the loop step.
• Crash / ASan heap-buffer-overflow. You read past n. Rebuild with cc -std=c11 -fsanitize=address,undefined -g and rerun; ASan names the exact out-of-bounds read. Verify the i + 8 <= n guard and the n % 8 check.
• Everything returns -1. Your length is not a multiple of 8, or you passed NULL. Print n and (void*)frame before the guard.
• Want to see a real canary? Compile a tiny program with -fstack-protector-strong -g, run under gdb, break in a function with a local array, and x/8xb $rbp-8 (approx) to inspect the canary word; compare its low byte to 0x00. Do this only on your own lab machine.

Questions to ask when it fails:

1. Is the snapshot length a multiple of 8, and did I reject it if not?
2. Am I reading the low byte at index 0 (little-endian) or wrongly at index 7?
3. Does my match require BOTH the null low byte and upper-byte entropy?
4. Am I within bounds on the last slot (i + 8 <= n)?
5. Have I run it under ASan/UBSan to rule out silent out-of-bounds reads?

Memory safety

Security & safety — detection, logging, and memory hygiene.

Memory safety of the detector itself. The tool is read-only: frame is const uint8_t *, never written. Safety hinges on (a) rejecting NULL and non-multiple-of-8 lengths, (b) the i + 8 <= n bound so slot[0..7] is always in range, and (c) never assuming the snapshot is NUL-terminated (it is raw bytes, not a string — do not use str* functions on it). Build and CI-test it under -fsanitize=address,undefined so any accidental over-read is caught.

What to log when this detector or a runtime canary check fires.

• Log: timestamp (UTC), source of the snapshot (dump id / process / host you are authorized to analyze), the resource inspected (binary + function or frame offset), the result (candidate canary at offset 0x... or none), the security decision (flagged / cleared), and a correlation id tying it to the analysis case. For runtime SSP aborts, log the process, the __stack_chk_fail / SIGABRT event, and the faulting function if symbolized.
• Never log: the raw canary value or full frame contents (the canary is a per-process secret — leaking it defeats the mitigation), plus any passwords, tokens, session cookies, private keys, full PANs, or PII that might sit in the captured frame. Log offsets and verdicts, not secret bytes.

Which events signal abuse. Repeated *** stack smashing detected *** / __stack_chk_fail aborts in a service — especially clustered on one endpoint or from one source — suggest active overflow attempts and warrant alerting. A canary that changed value across runs is expected (it is randomized per process); a canary check that fails is the signal.

How false positives arise. The byte heuristic matches any 8-byte word with a null low byte and non-zero upper bytes — pointers, small integers, and struct padding can all fit. Treat matches as candidates, corroborate with frame layout and a debugger, and never claim a system is "secure" because a canary is present: SSP is one detection control, not a proof of memory safety.

Real-world uses

Authorized real-world use case. A security engineer auditing a vendor-supplied binary (that their org owns or is contractually authorized to test) captures a stack-frame snapshot from a core dump and runs a canary detector as part of a hardening report: "Function parse_record places a canary at frame offset 0x30 — SSP is active," or the opposite, flagging a build that shipped with -fno-stack-protector. This feeds a remediation ticket: rebuild with -fstack-protector-strong and re-verify.

Mitigation verification (prove the control works). After enabling stack protection, confirm it: (1) checksec --file=./app (or readelf/objdump) should report Canary found; (2) in the disassembly, functions with buffers should load %fs:0x28 in the prologue and call __stack_chk_fail in the epilogue; (3) in a lab, an overflow test that previously hijacked control should now abort with *** stack smashing detected ***. Re-run these after each build.

Best-practice habits.

• Validation: reject malformed snapshots (NULL, wrong length) before processing.
• Least privilege: run analysis tools as an unprivileged user on a dedicated analysis host; do not run untrusted binaries.
• Secure defaults: build all C services with -fstack-protector-strong -D_FORTIFY_SOURCE=2 -O2, PIE, and RELRO; treat SSP as one layer, not the whole defense.
• Logging & error handling: record verdicts and offsets with a correlation id; never log the canary value or frame secrets.

Beginner vs advanced.

• Beginner: run checksec on your own compiled binaries; write and test the byte-pattern detector on synthetic snapshots.
• Advanced: symbolize core dumps, correlate canary offsets with the frame layout the compiler emitted, distinguish accidental corruption from overflow attempts, and integrate SSP-abort telemetry into detection pipelines — all on systems you own or are authorized to test.

Practice tasks

All tasks are lab-only: use synthetic snapshots or binaries you compiled yourself on localhost / a container / an intentionally-vulnerable VM. Authorization checklist before any hands-on step: (1) you own or have explicit written authorization for the target; (2) it is isolated (no third-party systems, no production data); (3) you know the reset/cleanup steps. Every task ends by remediating and verifying — never by leaving a system exploitable.

Beginner 1 — Single-slot classifier.

• Objective: implement int is_canary_slot(const uint8_t slot[8]) returning 1 for the canary shape, else 0.
• Requirements: low byte 0x00 AND at least one of bytes 1..7 non-zero.
• I/O: input 8 bytes; output 0/1.
• Constraints: no writes to slot; C11.
• Hints: one boolean for the low byte, a small loop for the upper bytes.
• Concepts: byte patterns, terminator canary.

Beginner 2 — Verify SSP on your own build.

• Objective: prove a binary you compiled has a canary.
• Requirements: build one program with -fstack-protector-strong and one with -fno-stack-protector; run checksec --file=./prog (or inspect with objdump -d for __stack_chk_fail) on each and record the difference.
• Constraints: your own lab machine only.
• Hints: look for %fs:0x28 in the prologue.
• Defensive conclusion: document which build is hardened and note that the unhardened one should be rebuilt. Cleanup: delete both test binaries.
• Concepts: mitigation verification, secure defaults.

Intermediate 1 — Report all matching offsets.

• Objective: extend the detector to fill a caller array with the byte offset of every canary-shaped slot and return the count.
• Requirements: signature int find_canary_offsets(const uint8_t *frame, size_t n, size_t *out, size_t out_cap); validate input; never exceed out_cap; return -1 on bad input.
• I/O: frame + capacity in; offsets + count out.
• Constraints: aligned iteration; no over-read.
• Hints: stop writing to out once you hit out_cap but keep counting.
• Concepts: bounds safety, pointers.

Intermediate 2 — False-positive study.

• Objective: quantify the heuristic's false-positive rate.
• Requirements: generate N random 8-byte words, count how many match the canary shape by chance, and compare to the expected rate (~ (1/256) for the null low byte, minus the all-zero case).
• I/O: N in; observed vs expected rate out.
• Constraints: seed the RNG for reproducibility; do not use randomness as a security control.
• Hints: P(low byte 0) = 1/256; subtract the negligible all-zero probability.
• Defensive conclusion: write one sentence on why a match is a candidate, not proof, and how you would corroborate it.
• Concepts: heuristics, false positives.

Challenge — Snapshot triage tool with logging.

• Objective: build a command-line tool that reads a snapshot file, reports candidate canary offsets, and writes a safe audit log.
• Requirements: validate the file length is a multiple of 8; for each candidate log timestamp, source file, offset, and verdict with a correlation id; never log the canary bytes or full frame contents. Include a --verify note reminding the user to corroborate in a debugger.
• Constraints: read-only on the snapshot; lab data only.
• Hints: reuse find_canary_offsets; keep secrets out of the log.
• Defensive conclusion: the tool must state that a candidate is not proof and recommend rebuilding any binary found without canaries, then re-running verification. Cleanup: remove test snapshots and rotate/delete the audit log after the exercise.
• Concepts: detection & logging, least privilege, mitigation verification.

Summary

Main concepts. A stack canary is a random machine word the compiler places between a function's locals and its saved return address; the epilogue compares it against the per-process secret and aborts via __stack_chk_fail if a linear buffer overflow corrupted it. The protected asset is the saved return address; the canary makes tampering detectable, it does not prevent the overflow. On glibc x86_64 it is a terminator canary: low byte 0x00, upper 7 bytes random.

Key syntax/commands. Detector shape: validate frame != NULL and n % 8 == 0, iterate for (i = 0; i + 8 <= n; i += 8), match a slot when slot[0] == 0 AND some slot[1..7] != 0. Verify SSP with checksec --file=./prog, objdump -d (__stack_chk_fail, %fs:0x28), and build with -fstack-protector-strong.

Common mistakes. Flagging all-zero words; unaligned byte-by-byte scanning; reading past the buffer; checking the wrong byte for endianness; claiming a match proves a canary.

What to remember. This is a read-only, defensive heuristic detector run only on authorized snapshots. Log offsets and verdicts, never the canary value. A present canary is one detection layer — decoding a signature or passing a scan never proves a system is "secure."

Practice with these exercises

• Is the canary intact?
• Is it a terminator canary?
• Detect a glibc-style stack canary pattern