Disclosed herein are system, method, and computer program product embodiments for propagating taint information for strings using metadata. Taint information for a string is encoded using taint ranges. When an operation is performed on the string, the operation and any additional taint information corresponding to the operation is encoded into a delta layer of the metadata. Rather than immediately obtaining taint information for a result string when the operation is performed on the string, the delta layer stores the taint information for the operation, and any subsequent operation, until it is needed. Once the taint information is needed, then the delta layers are collapsed into base layer taint information in order to resolve taint information for a result string.