| 2022-02-22 - debugging options with pools |
| |
| Two goals: |
| - help developers spot bugs as early as possible |
| |
| - make the process more reliable in field, by killing sick ones as soon as |
| possible instead of letting them corrupt data, cause trouble, or even be |
| exploited. |
| |
| An allocated object may exist in 5 forms: |
| - in use: currently referenced and used by haproxy, 100% of its size are |
| dedicated to the application which can do absolutely anything with it, |
| but it may never touch anything before nor after that area. |
| |
| - in cache: the object is neither referenced nor used anymore, but it sits |
| in a thread's cache. The application may not touch it at all anymore, and |
| some parts of it could even be unmapped. Only the current thread may safely |
| reach it, though others might find/release it when under thread isolation. |
| The thread cache needs some LRU linking that may be stored anywhere, either |
| inside the area, or outside. The parts surrounding the <size> parts remain |
| invisible to the application layer, and can serve as a protection. |
| |
| - in shared cache: the object is neither referenced nor used anymore, but it |
| may be reached by any thread. Some parts of it could be unmapped. Any |
| thread may pick it but only one may find it, hence once grabbed, it is |
| guaranteed no other one will find it. The shared cache needs to set up a |
| linked list and a single pointer needs to be stored anywhere, either inside |
| or outside the area. The parts surrounding the <size> parts remain |
| invisible to the application layer, and can serve as a protection. |
| |
| - in the system's memory allocator: the object is not known anymore from |
| haproxy. It may be reassigned in parts or totally to other pools or other |
| subsystems (e.g. crypto library). Some or all of it may be unmapped. The |
| areas surrounding the <size> parts are also part of the object from the |
| library's point of view and may be delivered to other areas. Tampering |
| with these may cause any other part to malfunction in dirty ways. |
| |
| - in the OS only: the memory allocator gave it back to the OS. |
| |
| The following options need to be configurable: |
| - detect improper initialization: this is done by poisonning objects before |
| delivering them to the application. |
| |
| - help figure where an object was allocated when in use: a pointer to the |
| call place will help. Pointing to the last pool_free() as well for the |
| same reasons when dealing with a UAF. |
| |
| - detection of wrong pointer/pool when in use: a pointer to the pool before |
| or after the area will definitely help. |
| |
| - detection of overflows when in use: a canary at the end of the area |
| (closest possible to <size>) will definitely help. The pool above can do |
| that job. Ideally, we should fill some data at the end so that even |
| unaligned sizes can be checked (e.g. a buffer that gets a zero appended). |
| If we just align on 2 pointers, writing the same pointer twice at the end |
| may do the job, but we won't necessarily have our bytes. Thus a particular |
| end-of-string pattern would be useful (e.g. ff55aa01) to fill it. |
| |
| - detection of double free when in cache: similar to detection of wrong |
| pointer/pool when in use: the pointer at the end may simply be changed so |
| that it cannot match the pool anymore. By using a pointer to the caller of |
| the previous free() operation, we have the guarantee to see different |
| pointers, and this pointer can be inspected to figure where the object was |
| previously freed. An extra check may even distinguish a perfect double-free |
| (same caller) from just a wrong free (pointer differs from pool). |
| |
| - detection of late corruption when in cache: keeping a copy of the |
| checksum of the whole area upon free() will do the job, but requires one |
| extra storage area for the checksum. Filling the area with a pattern also |
| does the job and doesn't require extra storage, but it loses the contents |
| and can be a bit slower. Sometimes losing the contents can be a feature, |
| especially when trying to detect late reads. Probably that both need to |
| be implemented. Note that if contents are not strictly needed, storing a |
| checksum inside the area does the job. |
| |
| - preserve total contents in cache for debugging: losing some precious |
| information can be a problem. |
| |
| - pattern filling of the area helps detect use-after-free in read-only mode. |
| |
| - allocate cold first helps with both cases above. |
| |
| Uncovered: |
| - overflow/underflow when in cache/shared/libc: it belongs to use-after-free |
| pattern and such an error during regular use ought to be caught while the |
| object was still in use. |
| |
| - integrity when in libc: not under our control anymore, this is a libc |
| problem. |
| |
| Arbitrable: |
| - integrity when in shared cache: unlikely to happen only then if it could |
| have happened in the local cache. Shared cache not often used anymore, thus |
| probably not worth the effort |
| |
| - protection against double-free when in shared cache/libc: might be done for |
| a cheap price, probably worth being able to quickly tell that such an |
| object left the local cache (e.g. the mark points to the caller, but could |
| possibly just be incremented, hence still point to the same code location+1 |
| byte when released. Calls are 4 bytes min on RISC, 5 on x86 so we do have |
| some margin by having a caller's location be +0,+1,+2 or +3. |
| |
| - underflow when in use: hasn't been really needed over time but may change. |
| |
| - detection of late corruption when in shared cache: checksum or area filling |
| are possible, but is this as relevant as it used to considering the less |
| common use of the shared cache ? |
| |
| Design considerations: |
| - object allocation when in use must remain minimal |
| |
| - when in cache, there are 2 lists which the compiler expect to be at least |
| aligned each (e.g. if/when we start to use DWCAS). |
| |
| - the original "pool debugging" feature covers both pool tracking, double- |
| free detection, overflow detection and caller info at the cost of a single |
| pointer placed immediately after the area. |
| |
| - preserving the contents might be done by placing the cache links and the |
| shared cache's list outside of the area (either before or after). Placing |
| it before has the merit that the allocated object preserves the 4-ptr |
| alignment. But when a larger alignment is desired this often does not work |
| anymore. Placing it after requires some dynamic adjustment depending on the |
| object's size. If any protection is installed, this protection must be |
| placed before the links so that the list doesn't get randomly corrupted and |
| corrupts adjacent elements. Note that if protection is desired, the extra |
| waste is probably less critical. |
| |
| - a link to the last caller might have to be stored somewhere. Without |
| preservation the free() caller may be placed anywhere while the alloc() |
| caller may only be placed outside. With preservation, again the free() |
| caller may be placed either before the object or after the mark at the end. |
| There is no particular need that both share the same location though it may |
| help. Note that when debugging is enabled, the free() caller doesn't need |
| to be duplicated and can continue to serve as the double-free detection. |
| Thus maybe in the end we only need to store the caller to the last alloc() |
| but not the free() since if we want it it's available via the pool debug. |
| |
| - use-after-free detection: contents may be erased on free() and checked on |
| alloc(), but they can also be checksummed on free() and rechecked on |
| alloc(). In the latter case we need to store a checksum somewhere. Note |
| that with pure checksum we don't know what part was modified, but seeing |
| previous contents can be useful. |
| |
| Possibilities: |
| |
| 1) Linked lists inside the area: |
| |
| V size alloc |
| ---+------------------------------+-----------------+-- |
| in use |##############################| (Pool) (Tracer) | |
| ---+------------------------------+-----------------+-- |
| |
| ---+--+--+------------------------+-----------------+-- |
| in cache |L1|L2|########################| (Caller) (Sum) | |
| ---+--+--+------------------------+-----------------+-- |
| or: |
| ---+--+--+------------------------+-----------------+-- |
| in cache |L1|L2|###################(sum)| (Caller) | |
| ---+--+--+------------------------+-----------------+-- |
| |
| ---+-+----------------------------+-----------------+-- |
| in global |N|XXXX########################| (Caller) | |
| ---+-+----------------------------+-----------------+-- |
| |
| |
| 2) Linked lists before the the area leave room for tracer and pool before |
| the area, but the canary must remain at the end, however the area will |
| be more difficult to keep aligned: |
| |
| V head size alloc |
| ----+-+-+------------------------------+-----------------+-- |
| in use |T|P|##############################| (canary) | |
| ----+-+-+------------------------------+-----------------+-- |
| |
| --+-----+------------------------------+-----------------+-- |
| in cache |L1|L2|##############################| (Caller) (Sum) | |
| --+-----+------------------------------+-----------------+-- |
| |
| ------+-+------------------------------+-----------------+-- |
| in global |N|##############################| (Caller) | |
| ------+-+------------------------------+-----------------+-- |
| |
| |
| 3) Linked lists at the end of the area, might be shared with extra data |
| depending on the state: |
| |
| V size alloc |
| ---+------------------------------+-----------------+-- |
| in use |##############################| (Pool) (Tracer) | |
| ---+------------------------------+-----------------+-- |
| |
| ---+------------------------------+--+--+-----------+-- |
| in cache |##############################|L1|L2| (Caller) (Sum) |
| ---+------------------------------+--+--+-----------+-- |
| |
| ---+------------------------------+-+---------------+-- |
| in global |##############################|N| (Caller) | |
| ---+------------------------------+-+---------------+-- |
| |
| This model requires a little bit of alignment at the end of the area, which is |
| not incompatible with pattern filling and/or checksumming: |
| - preserving the area for post-mortem analysis means nothing may be placed |
| inside. In this case it could make sense to always store the last releaser. |
| - detecting late corruption may be done either with filling or checksumming, |
| but the simple fact of assuming a risk of corruption that needs to be |
| chased means we must not store the lists nor caller inside the area. |
| |
| Some models imply dedicating some place when in cache: |
| - preserving contents forces the lists to be prefixed or appended, which |
| leaves unused places when in use. Thus we could systematically place the |
| pool pointer and the caller in this case. |
| |
| - if preserving contents is not desired, almost everything can be stored |
| inside when not in use. Then each situation's size should be calculated |
| so that the allocated size is known, and entries are filled from the |
| beginning while not in use, or after the size when in use. |
| |
| - if poisonning is requested, late corruption might be detected but then we |
| don't want the list to be stored inside at the risk of being corrupted. |
| |
| Maybe just implement a few models: |
| - compact/optimal: put l1/l2 inside |
| - detect late corruption: fill/sum, put l1/l2 out |
| - preserve contents: put l1/l2 out |
| - corruption+preserve: do not fill, sum out |
| - poisonning: not needed on free if pattern filling is done. |
| |
| try2: |
| - poison on alloc to detect missing initialization: yes/no |
| (note: nothing to do if filling done) |
| - poison on free to detect use-after-free: yes/no |
| (note: nothing to do if filling done) |
| - check on alloc for corruption-after-free: yes/no |
| If content-preserving => sum, otherwise pattern filling; in |
| any case, move L1/L2 out. |
| - check for overflows: yes/no: use a canary after the area. The |
| canary can be the pointer to the pool. |
| - check for alloc caller: yes/no => always after the area |
| - content preservation: yes/no |
| (disables filling, moves lists out) |
| - improved caller tracking: used to detect double-free, may benefit |
| from content-preserving but not only. |