From patchwork Mon Jun 21 19:18:29 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: James Carter X-Patchwork-Id: 12335547 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2A106C49EA2 for ; Mon, 21 Jun 2021 19:18:46 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0A6CA61040 for ; Mon, 21 Jun 2021 19:18:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231288AbhFUTU7 (ORCPT ); Mon, 21 Jun 2021 15:20:59 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:39988 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231134AbhFUTU7 (ORCPT ); Mon, 21 Jun 2021 15:20:59 -0400 Received: from mail-qt1-x82a.google.com (mail-qt1-x82a.google.com [IPv6:2607:f8b0:4864:20::82a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B5658C061756 for ; Mon, 21 Jun 2021 12:18:43 -0700 (PDT) Received: by mail-qt1-x82a.google.com with SMTP id e3so14375573qte.0 for ; Mon, 21 Jun 2021 12:18:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=i7HAfMW+B1XJvbDs0vNOvjIbN8XUyOGzoA5qXa9JGTg=; b=puFkAzHJLN4bnXWcD0BAQgp+ZzSltc3GiQJ+7vdB6dk8hh6z27ALMV7FXYlV55IUJM CfKN2RaeowIT1WXHTocp/6ldvkrzZl4fntPS5gyfcC5ugAfrSI3Bg0sKdpF1KjVBxmus c+r1qbqbGv3dpK4UxHKj8XEXPxGFy99OXwtLDZgYATJv4tmp+TKthgJgqcgEDXzKxoLX btr1o6CtYBcs2mX4YgdHgy1bBC97UO68k1yLTv1eiN9D7eKZjh38P4dF1kQOXjfpgzD9 kGv9gDh2qheyHQh7+hfQ9CTXlZOcQpzNwdl08gG06TKZvJt24VHOcoFyCKJ9N4nb3/IA 6R8w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=i7HAfMW+B1XJvbDs0vNOvjIbN8XUyOGzoA5qXa9JGTg=; b=QL8+4YliRfOXz2/hGI3ZQqA1CMJYWn1HxPFx7S6yupJx2Q9D/+yAZDoyKKVMRFSTYc 0D0k/359OO7qPt5OF76Mvb41vcf2LG1kmmN7+skDz+02AOwi6wHi7rDH2KWII+uU25Tn qW5F0ZnutNoUn5VTmK2+rH+lITyT1B3U9C0pOcO8spozt446FTD+5aM6zFC0qNbZkUlT hSuhcQvEQFPne+i+7hrDiVXG91zV15UmhvwJsrZB713jk+qOrPUQTV573t1VN2tlnrFv v12LD+jImnDyTsDt/mhc5r0NWT07CAa3EDUUx2lslRiB8oA5UbUz33LIdDDAmO7QoZtH LaKA== X-Gm-Message-State: AOAM531M2oKyrGX0Jxe7SiBX5r7Ej/qWDpPKVpU6LCIzHAjX4fYtqd/n wTGxEXt/4TFw7Tddyz6Pk8rxRA3bAsjyag== X-Google-Smtp-Source: ABdhPJylXc49msBUCk1+wugvDWV2P5KYUPSCA+fC3L0wYUfj+Wz5ZJjB1qs446zvTo3tXDRkgZwQPg== X-Received: by 2002:ac8:5755:: with SMTP id 21mr71597qtx.267.1624303122803; Mon, 21 Jun 2021 12:18:42 -0700 (PDT) Received: from localhost.localdomain (c-73-200-157-122.hsd1.md.comcast.net. [73.200.157.122]) by smtp.gmail.com with ESMTPSA id o5sm10449124qkl.25.2021.06.21.12.18.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Jun 2021 12:18:42 -0700 (PDT) From: James Carter To: selinux@vger.kernel.org Cc: nicolas.iooss@m4x.org, James Carter Subject: [PATCH 1/5 v2] libsepol/cil: Properly check for loops in sets Date: Mon, 21 Jun 2021 15:18:29 -0400 Message-Id: <20210621191833.282874-2-jwcart2@gmail.com> X-Mailer: git-send-email 2.26.3 In-Reply-To: <20210621191833.282874-1-jwcart2@gmail.com> References: <20210621191833.282874-1-jwcart2@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org Commit 61fbdce666f24c4a118b249ece6b014d54b65074 (ibsepol/cil: Check for self-referential loops in sets) added checks for self-referential loops in user, role, type, and category sets. Unfortunately, this check ends up in an infinite loop if the set with the self-referential loop is used in a different set that is checked before the bad set. The problem with the old check is that only the initial datum is used for the check. Instead, use a stack to track all of the set datums that are currently involved as the check is made. A self-referential loop occurs if a duplicate datum is found for any of the datums in the stack. Signed-off-by: James Carter Acked-by: Nicolas Iooss --- libsepol/cil/src/cil_verify.c | 48 +++++++++++++++++++++++------------ 1 file changed, 32 insertions(+), 16 deletions(-) diff --git a/libsepol/cil/src/cil_verify.c b/libsepol/cil/src/cil_verify.c index 8e15a0e6..59397f70 100644 --- a/libsepol/cil/src/cil_verify.c +++ b/libsepol/cil/src/cil_verify.c @@ -44,6 +44,7 @@ #include "cil_tree.h" #include "cil_list.h" #include "cil_find.h" +#include "cil_stack.h" #include "cil_verify.h" @@ -430,9 +431,9 @@ int cil_verify_decl_does_not_shadow_macro_parameter(struct cil_macro *macro, str return SEPOL_OK; } -static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_symtab_datum *orig); +static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_stack *stack); -static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_symtab_datum *orig) +static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_stack *stack) { struct cil_list_item *item; int rc = SEPOL_OK; @@ -444,9 +445,9 @@ static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_ cil_list_for_each(item, expr) { if (item->flavor == CIL_DATUM) { struct cil_symtab_datum* datum = item->data; - rc = cil_verify_no_self_reference(FLAVOR(datum), datum, orig); + rc = cil_verify_no_self_reference(FLAVOR(datum), datum, stack); } else if (item->flavor == CIL_LIST) { - rc = __verify_no_self_reference_in_expr(item->data, orig); + rc = __verify_no_self_reference_in_expr(item->data, stack); } if (rc != SEPOL_OK) { return SEPOL_ERR; @@ -456,36 +457,47 @@ static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_ return SEPOL_OK; } -static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_symtab_datum *orig) +static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_stack *stack) { + struct cil_stack_item *item; + int i = 0; int rc = SEPOL_OK; - if (datum == orig) { - cil_tree_log(NODE(orig), CIL_ERR, "Self-reference found for %s", orig->name); - return SEPOL_ERR; - } else if (orig == NULL) { - orig = datum; + cil_stack_for_each(stack, i, item) { + struct cil_symtab_datum *prev = item->data; + if (datum == prev) { + cil_tree_log(NODE(datum), CIL_ERR, "Self-reference found for %s", datum->name); + return SEPOL_ERR; + } } switch (flavor) { case CIL_USERATTRIBUTE: { struct cil_userattribute *attr = (struct cil_userattribute *)datum; - rc = __verify_no_self_reference_in_expr(attr->expr_list, orig); + cil_stack_push(stack, CIL_DATUM, datum); + rc = __verify_no_self_reference_in_expr(attr->expr_list, stack); + cil_stack_pop(stack); break; } case CIL_ROLEATTRIBUTE: { struct cil_roleattribute *attr = (struct cil_roleattribute *)datum; - rc = __verify_no_self_reference_in_expr(attr->expr_list, orig); + cil_stack_push(stack, CIL_DATUM, datum); + rc = __verify_no_self_reference_in_expr(attr->expr_list, stack); + cil_stack_pop(stack); break; } case CIL_TYPEATTRIBUTE: { struct cil_typeattribute *attr = (struct cil_typeattribute *)datum; - rc = __verify_no_self_reference_in_expr(attr->expr_list, orig); + cil_stack_push(stack, CIL_DATUM, datum); + rc = __verify_no_self_reference_in_expr(attr->expr_list, stack); + cil_stack_pop(stack); break; } case CIL_CATSET: { struct cil_catset *set = (struct cil_catset *)datum; - rc = __verify_no_self_reference_in_expr(set->cats->datum_expr, orig); + cil_stack_push(stack, CIL_DATUM, datum); + rc = __verify_no_self_reference_in_expr(set->cats->datum_expr, stack); + cil_stack_pop(stack); break; } default: @@ -1826,9 +1838,13 @@ int __cil_pre_verify_helper(struct cil_tree_node *node, uint32_t *finished, __at case CIL_USERATTRIBUTE: case CIL_ROLEATTRIBUTE: case CIL_TYPEATTRIBUTE: - case CIL_CATSET: - rc = cil_verify_no_self_reference(node->flavor, node->data, NULL); + case CIL_CATSET: { + struct cil_stack *stack; + cil_stack_init(&stack); + rc = cil_verify_no_self_reference(node->flavor, node->data, stack); + cil_stack_destroy(&stack); break; + } default: rc = SEPOL_OK; break; From patchwork Mon Jun 21 19:18:30 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: James Carter X-Patchwork-Id: 12335545 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A207BC49EA4 for ; Mon, 21 Jun 2021 19:18:46 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 880A761040 for ; Mon, 21 Jun 2021 19:18:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231134AbhFUTVA (ORCPT ); Mon, 21 Jun 2021 15:21:00 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:39990 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231247AbhFUTU7 (ORCPT ); Mon, 21 Jun 2021 15:20:59 -0400 Received: from mail-qk1-x72b.google.com (mail-qk1-x72b.google.com [IPv6:2607:f8b0:4864:20::72b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7FD65C061574 for ; Mon, 21 Jun 2021 12:18:44 -0700 (PDT) Received: by mail-qk1-x72b.google.com with SMTP id q64so26985866qke.7 for ; Mon, 21 Jun 2021 12:18:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=J+9V/oOcCyNF4Rtzxy+MS9gurKu16Ed+6uLPweXPw/I=; b=tp4/ygQmAtnqyjM2fwhZjZzwrK1LiSY+bRANWR8vjDFltrOrtzRbobE7NXjwh37vdX CQ/2S64duKcnVyTxTSQ2NQB16Nbpuf5FFGp5xRd1PR4kwM7mKJSHtYBuEsH0EMMSUDZF rcKn66hmIZXN4zShHAbjEDdHuaCDMp8KRrT0XKPLCuHqPDRssxuagvQsc9yp74uwg59Q fejcEt+u6nHqOqYlx629FwBHocks5S7j9Na3DjLhfNVX3awgdDZaFAM5SAy+ykYArrXP KRhkJE1ILWPXLl0QytU8BOf8zNOYfFXAUZtxcV2zFbJ510jHmPaOBbzD1gqFY4WcO247 wKCQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=J+9V/oOcCyNF4Rtzxy+MS9gurKu16Ed+6uLPweXPw/I=; b=tEWIM83aGWpDptgu7S0tYLvB7geHammkv0hvqwMv+I4bnw03BL9RgrIxp6R3G8hcDA Tn4IviVMjcvoEpjbsoQ2j0WuqHlUzKr+qkbjrn31xlif64Jgs4retxs9pOiVhfuKtHxO hcN6tjvIMdMQGyKtme3xL7+Bgr/7UyAl11aXhMZ3sOLAwDjenw10944mKdmcr1GIMDwy YV9BbOlHlARwAy+E41shTUFqnSb/TDqrb0AKphjG0OMuVImKueNMlgHe4m8uM7N5hdQu 4/tp2fLGDB3ddW3S8jJsmeAmnfdhYqGQDZMev4s8luyTxsgzw6fUlT9KBVloSXE7TTCi s5/w== X-Gm-Message-State: AOAM531elumD+I8WkAtFU0hZUmO+uW/EHBk7lfuNF12uMmH2hjV2LQ1T MLzZ6yECw23NVPUbS6KOTU/gHkDnx2bnIQ== X-Google-Smtp-Source: ABdhPJyAPXg3rEVQCv6WfTKL21D/RoH+v8i07L3c6OOcqkwJfljqzKURfq0hB9dgjrK2iiZFVfqyyg== X-Received: by 2002:a05:620a:91c:: with SMTP id v28mr173513qkv.249.1624303123470; Mon, 21 Jun 2021 12:18:43 -0700 (PDT) Received: from localhost.localdomain (c-73-200-157-122.hsd1.md.comcast.net. [73.200.157.122]) by smtp.gmail.com with ESMTPSA id o5sm10449124qkl.25.2021.06.21.12.18.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Jun 2021 12:18:43 -0700 (PDT) From: James Carter To: selinux@vger.kernel.org Cc: nicolas.iooss@m4x.org, James Carter Subject: [PATCH 2/5 v2] libsepol/cil: Fix syntax checking of defaultrange rule Date: Mon, 21 Jun 2021 15:18:30 -0400 Message-Id: <20210621191833.282874-3-jwcart2@gmail.com> X-Mailer: git-send-email 2.26.3 In-Reply-To: <20210621191833.282874-1-jwcart2@gmail.com> References: <20210621191833.282874-1-jwcart2@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org When "glblub" was added as a default for the defaultrange rule, the syntax array was updated because the "glblub" default does not need to specify a range of "low", "high", or "low-high". Unfortunately, additional checking was not added for the "source" and "target" defaults to make sure they specified a range. This means that using the "source" or "target" defaults without specifying the range will result in a segfault. When the "source" or "target" defaults are used, check that the rule specifies a range as well. This bug was found by the secilc-fuzzer. Signed-off-by: James Carter --- v2: Take the glblub option into account and fix the syntax checking a different way libsepol/cil/src/cil_build_ast.c | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/libsepol/cil/src/cil_build_ast.c b/libsepol/cil/src/cil_build_ast.c index 71f14e20..178ec2e5 100644 --- a/libsepol/cil/src/cil_build_ast.c +++ b/libsepol/cil/src/cil_build_ast.c @@ -5886,6 +5886,11 @@ int cil_gen_defaultrange(struct cil_tree_node *parse_current, struct cil_tree_no object = parse_current->next->next->data; if (object == CIL_KEY_SOURCE) { + if (!parse_current->next->next->next) { + cil_log(CIL_ERR, "Missing 'low', 'high', or 'low-high'\n"); + rc = SEPOL_ERR; + goto exit; + } range = parse_current->next->next->next->data; if (range == CIL_KEY_LOW) { def->object_range = CIL_DEFAULT_SOURCE_LOW; @@ -5899,6 +5904,11 @@ int cil_gen_defaultrange(struct cil_tree_node *parse_current, struct cil_tree_no goto exit; } } else if (object == CIL_KEY_TARGET) { + if (!parse_current->next->next->next) { + cil_log(CIL_ERR, "Missing 'low', 'high', or 'low-high'\n"); + rc = SEPOL_ERR; + goto exit; + } range = parse_current->next->next->next->data; if (range == CIL_KEY_LOW) { def->object_range = CIL_DEFAULT_TARGET_LOW; From patchwork Mon Jun 21 19:18:31 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: James Carter X-Patchwork-Id: 12335549 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 400A0C48BC2 for ; Mon, 21 Jun 2021 19:18:47 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 2C3A061040 for ; Mon, 21 Jun 2021 19:18:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231367AbhFUTVA (ORCPT ); Mon, 21 Jun 2021 15:21:00 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:39996 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231157AbhFUTVA (ORCPT ); Mon, 21 Jun 2021 15:21:00 -0400 Received: from mail-qt1-x829.google.com (mail-qt1-x829.google.com [IPv6:2607:f8b0:4864:20::829]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E7633C06175F for ; Mon, 21 Jun 2021 12:18:44 -0700 (PDT) Received: by mail-qt1-x829.google.com with SMTP id r20so14331303qtp.3 for ; Mon, 21 Jun 2021 12:18:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=/IgRyB42VS88SbqUKS+oTD/XtOocKdBJMFO6W6uIP+g=; b=CcPJUFzCg+bCZJBcYSDQX6H1PEhbJvRRVCmEE7w7OzIJXnFXNU9eKbrNJSYOK0YCR4 m9hLSQ4S73Te9Qe2iHlEWWq3hkFzRqtAXBoun7xoYBeM+W27G3HLVoJbbrgFokMXZs6I ASRfbulsoQZeFMBeul2aKppYfPRFFr7V96a7UpqL4/pGNuiqtAaao/GcxDrgYxE+INWH sNsrq/qJCgJ3YQGxTlIjCbfi2p0vLS8IiwFIWoRGfDiCCS0m5+ybwmwLDvg+Dvm58fx4 qZWTUltcX80ZNig7ztKG82kV10v/3gmWNDMMcrgGKmRQQxiNMhGV1qh0uEmRSj3lep6u iI6A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=/IgRyB42VS88SbqUKS+oTD/XtOocKdBJMFO6W6uIP+g=; b=hXtdnX0X83MGFd7iNsbCCEMlGaNPsQl6pAR7hFYU+Ub9xg7neCBi0AeZ8W8b2QrtEl vg98YNk7r5yOGKVnpzoN+U8dV8+y5Ck0jb486row276QveaBxnFykiJYSxPzGOJ/B5+S XlHitRA1RYu1Y0aN+5jRQiyO9zWUDPd0tU179nOjuFQ7QRtsPm1CbJ+ytpAFZhoZN+Gw tNQOuG5DVrK3T+Kq9k6OfbauDOq4hHstuL7lH+fXUPp1g/LiGnOBfAWlWATX/GqFjNJy ZSnCfGfMvyDJruifZT+c7OuTNPtLL8IWjiw/ZGuAbOVp1t6bFr8vJq86K1/nX+hD/4e+ 78rA== X-Gm-Message-State: AOAM531OtT5vKUi/QTTIvDX4C9elNWLzw5efL2JNK2QhBcX1wqeypRvS DZ6G6XqrVBB2VbScftVtZcXI9kKsmxbpaw== X-Google-Smtp-Source: ABdhPJyjY4y+ljnTYwQFmOC+mj+angP6d5bMKBH0nZvq2CcofCwTFySGORgyKALylvVGK9NCmWj9hQ== X-Received: by 2002:a05:622a:486:: with SMTP id p6mr79049qtx.163.1624303124090; Mon, 21 Jun 2021 12:18:44 -0700 (PDT) Received: from localhost.localdomain (c-73-200-157-122.hsd1.md.comcast.net. [73.200.157.122]) by smtp.gmail.com with ESMTPSA id o5sm10449124qkl.25.2021.06.21.12.18.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Jun 2021 12:18:43 -0700 (PDT) From: James Carter To: selinux@vger.kernel.org Cc: nicolas.iooss@m4x.org, James Carter Subject: [PATCH 3/5 v2] libsepol/cil: Check for empty list when marking neverallow attributes Date: Mon, 21 Jun 2021 15:18:31 -0400 Message-Id: <20210621191833.282874-4-jwcart2@gmail.com> X-Mailer: git-send-email 2.26.3 In-Reply-To: <20210621191833.282874-1-jwcart2@gmail.com> References: <20210621191833.282874-1-jwcart2@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org When marking a type attribute as used in a neverallow (to help determine whether or not it should be expanded), check if the attribute's expression list is empty (no attributes are associated with it) before iterating over the list. Signed-off-by: James Carter Acked-by: Nicolas Iooss --- libsepol/cil/src/cil_post.c | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/libsepol/cil/src/cil_post.c b/libsepol/cil/src/cil_post.c index 05842b64..38544aef 100644 --- a/libsepol/cil/src/cil_post.c +++ b/libsepol/cil/src/cil_post.c @@ -1494,6 +1494,10 @@ static void __mark_neverallow_attrs(struct cil_list *expr_list) { struct cil_list_item *curr; + if (!expr_list) { + return; + } + cil_list_for_each(curr, expr_list) { if (curr->flavor == CIL_DATUM) { if (FLAVOR(curr->data) == CIL_TYPEATTRIBUTE) { From patchwork Mon Jun 21 19:18:32 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: James Carter X-Patchwork-Id: 12335551 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 05261C48BE5 for ; Mon, 21 Jun 2021 19:18:48 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E85A461040 for ; Mon, 21 Jun 2021 19:18:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231247AbhFUTVB (ORCPT ); Mon, 21 Jun 2021 15:21:01 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:39998 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231321AbhFUTVA (ORCPT ); Mon, 21 Jun 2021 15:21:00 -0400 Received: from mail-qk1-x72d.google.com (mail-qk1-x72d.google.com [IPv6:2607:f8b0:4864:20::72d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7D0D1C061760 for ; Mon, 21 Jun 2021 12:18:45 -0700 (PDT) Received: by mail-qk1-x72d.google.com with SMTP id j62so33270605qke.10 for ; Mon, 21 Jun 2021 12:18:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=V9XqI5wZGakGMMkN4si3z7paKzFX04xLDcWEiucRdVY=; b=rcE/r/cCxYy8agvCtfZYse3TloIxZjEtPKOwBYgy9Ib7N8DMIrgv4241gVclMtW5VR 4mFiepbObs4+wL6+AlzlW/DSoR2/VxdvXhSvFeFTCetMHVKfcO/nTk2ZaswWlgRQGp7k W9ALZFa0JOrDr0PKdaFc7pPQTSfgI3wPs/wVHZvU8+EKbjeI97l1Gi5/URJooJP15bvE u8CFg2aEVbnc3fcomHRrZrO1Mir01cN6J41qWU3G9gQ2nexCuzQ1nFHNkv6TqJZE6jRZ zpjJ4+NTuiqD9oibJqwWQbZQ1FP3zeaoNPTUClqrPVbirtvxvUHINSSr+IYCkkdYfwUW 52NQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=V9XqI5wZGakGMMkN4si3z7paKzFX04xLDcWEiucRdVY=; b=tz4wuQ4/cbjUupO52f/6I65flSa8h+WcKpDr1Mxtl8eMnZ2w0TpyeCYnQcihxDlS75 iriisVrfNv83veiWiKz3UJtifLN8GXlEw18vD6WywRyndHfF6GcCkrf+m0AVR1veoi9w MOLYcjj/tC5jK+tbDtuq4Ty+Z2NqqCcQeCfDDt7LTZngEGwhhIPJAiwCgNI0eJh1pbjz 6YSra8oF7hRbE2XNo2/kU+4mqykrvKnQ/Pxo7X+eI/AG35MGhZv8QPbVMmoupQFZfgk0 Hvb34dT3gZswr9k86Kj395sMXl+5oVGJGQ7XYRodl4M39ng2WGBcVPgVuF18bbjwB/sd fN1w== X-Gm-Message-State: AOAM533V0IKr9+Yk+8GNqIc1ahG1MaaSGLPQEQx7go5R00SGLHBkMmqW jpQZ8Dg2JY4aeRo0kNEb22DmY/fP3/E9Vw== X-Google-Smtp-Source: ABdhPJz2CZQgymaj/fhEA0fv+qzq2MKdPq1kImY1r+pa5jGnZAo2UPSrmgvaIbXHhmDfOstX1aKTyw== X-Received: by 2002:a37:bb82:: with SMTP id l124mr178901qkf.119.1624303124597; Mon, 21 Jun 2021 12:18:44 -0700 (PDT) Received: from localhost.localdomain (c-73-200-157-122.hsd1.md.comcast.net. [73.200.157.122]) by smtp.gmail.com with ESMTPSA id o5sm10449124qkl.25.2021.06.21.12.18.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Jun 2021 12:18:44 -0700 (PDT) From: James Carter To: selinux@vger.kernel.org Cc: nicolas.iooss@m4x.org, James Carter Subject: [PATCH 4/5 v2] libsepol/cil: Reduce the initial symtab sizes for blocks Date: Mon, 21 Jun 2021 15:18:32 -0400 Message-Id: <20210621191833.282874-5-jwcart2@gmail.com> X-Mailer: git-send-email 2.26.3 In-Reply-To: <20210621191833.282874-1-jwcart2@gmail.com> References: <20210621191833.282874-1-jwcart2@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org It is possible to create bad behaving policy that can consume all of a system's memory (one way is through the use of inheritance). Analyzing these policies shows that most of the memory usage is for the block symtabs. Most of the nineteen symtabs will most likely never be used, so give these symtabs an initial size of 1. The others are given more appropriate sizes. Signed-off-by: James Carter Acked-by: Nicolas Iooss --- libsepol/cil/src/cil.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libsepol/cil/src/cil.c b/libsepol/cil/src/cil.c index 0d351b49..c6674fc1 100644 --- a/libsepol/cil/src/cil.c +++ b/libsepol/cil/src/cil.c @@ -54,7 +54,7 @@ int cil_sym_sizes[CIL_SYM_ARRAY_NUM][CIL_SYM_NUM] = { {64, 64, 64, 1 << 13, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64}, - {64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64}, + {8, 8, 8, 32, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} From patchwork Mon Jun 21 19:18:33 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: James Carter X-Patchwork-Id: 12335553 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8018EC49EA5 for ; Mon, 21 Jun 2021 19:18:47 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6894F61040 for ; Mon, 21 Jun 2021 19:18:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231157AbhFUTVB (ORCPT ); Mon, 21 Jun 2021 15:21:01 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:39990 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231247AbhFUTVA (ORCPT ); Mon, 21 Jun 2021 15:21:00 -0400 Received: from mail-qk1-x72c.google.com (mail-qk1-x72c.google.com [IPv6:2607:f8b0:4864:20::72c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 175B0C061574 for ; Mon, 21 Jun 2021 12:18:46 -0700 (PDT) Received: by mail-qk1-x72c.google.com with SMTP id g142so33274959qke.4 for ; Mon, 21 Jun 2021 12:18:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=VOLAduFj40W7aUSByCgcAowRB3H1PJJpHqmocAr6BVw=; b=Eb3IR8eU+vGBv4S7IemaKbsLugcgET/cfA+sg4a8mpJr27QfuC2pyFMR0qyl537SPB y2+WcqvDnMTu7wbqi5HA+TVeYLWq8KZs6GhHzHPWXP6rR6+s51WrcqnGc57Al4FPxUvc iKi4KHd1CigHpdUpECImcC0OoNEWVzqVpw0W3oYB7su/s+mcVQZPqCKAXWY00tiRFZWz arVN72dNFezKKF7UuLzRvxhNebwy6eNxOBuUBq/zOGkExNU+q7z/gkOM8G+FnU+/wXDx bgl12qRjBUREtsyUmshzLiowH9dQ+ZCYY+3eeUU0IIt5DkPjahyMEBCIRi1Nq07kyZ5A wSxQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=VOLAduFj40W7aUSByCgcAowRB3H1PJJpHqmocAr6BVw=; b=phGmYjHWDZv4iSXSiJHcnASCMw+GeSAxKaDtn824m10GPbnLDRUnUxL2FyozkBOyG4 O/ryTQDbfBV6NLZbPieltTbHtouCWRw4Xmu8rmPn7yucGCbnYkhVNiKd2bABJlEbkyR6 FlE8Pc2hooPEPPzS5aDCiGSpHci1bmK8Em2eeY6uubApAIZMm9cJrTeTUU6LlpQFUPAx FSBJkXPiajCfnWAnV6XBnk753H1UurCnHvm7FYW3pS21SEWStz+6GtbiSFqCR7y3ddjC 5Nhxjyc3pbvJAdqEO33SfcwnLAUt83c2d1/sSpRXfidUB/ek09wbQcJ/i4QSAdVbSU1r JIWg== X-Gm-Message-State: AOAM531LzzTqTXh0PKtciLsnYJ1qNQjwOeGyDaI8fM15aoAB7rpsf6rV K+2/fmU/PtuBBKiscWc/JwLhCKIgvZqqtg== X-Google-Smtp-Source: ABdhPJyK3CP9t79octebD3UYI0JJO/a6iOz2hkQF0WEcyjnayblqFyawH7UUe4Dkl5Lsgm8cgvV9Hg== X-Received: by 2002:a05:620a:4516:: with SMTP id t22mr179049qkp.151.1624303125140; Mon, 21 Jun 2021 12:18:45 -0700 (PDT) Received: from localhost.localdomain (c-73-200-157-122.hsd1.md.comcast.net. [73.200.157.122]) by smtp.gmail.com with ESMTPSA id o5sm10449124qkl.25.2021.06.21.12.18.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Jun 2021 12:18:44 -0700 (PDT) From: James Carter To: selinux@vger.kernel.org Cc: nicolas.iooss@m4x.org, James Carter Subject: [PATCH 5/5 v2] libsepol/cil: Improve degenerate inheritance check Date: Mon, 21 Jun 2021 15:18:33 -0400 Message-Id: <20210621191833.282874-6-jwcart2@gmail.com> X-Mailer: git-send-email 2.26.3 In-Reply-To: <20210621191833.282874-1-jwcart2@gmail.com> References: <20210621191833.282874-1-jwcart2@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org The commit 74d00a8decebf940d95064ff60042dcb2cbcc2c0 (libsepol/cil: Detect degenerate inheritance and exit with an error) detects the use of inheritance (mostly by the secilc-fuzzer and not in any real policies) that results in the exponential growth of the policy through the copying of blocks that takes place with inheritance in CIL. Unfortunately, the check takes place during the pass when all the blocks are being copied, so it is possible to consume all of a system's memory before an error is produced. The new check happens in two parts. First, a check is made while the block inheritance is being linked to the block it will inherit. In this check, all of the parent nodes of the inheritance rule up to the root node are checked and if enough of these blocks are being inherited (>= CIL_DEGENERATE_INHERITANCE_DEPTH), then a flag is set for a more in-depth check after the pass. This in-depth check will determine the number of potential inheritances that will occur when resolving the all of the inheritance rules. If this value is greater than CIL_DEGENERATE_INHERITANCE_GROWTH * the original number of inheritance rules and greater than CIL_DEGENERATE_INHERITANCE_MINIMUM (which is set to 0x1 << CIL_DEGENERATE_INHERITANCE_DEPTH), then degenerate inheritance is determined to have occurred and an error result will be returned. Since the potential number of inheritances can quickly be an extremely large number, the count of potential inheritances is aborted as soon as the threshold for degenerate inheritance has been exceeded. Normal policies should rarely, if ever, have the in-depth check occur. Signed-off-by: James Carter --- v2: Move depth check into the while loop Only call cil_check_for_degenerate_inheritance() if value of inheritance_check is CIL_TRUE libsepol/cil/src/cil_internal.h | 5 +- libsepol/cil/src/cil_resolve_ast.c | 226 +++++++++++++++++++---------- 2 files changed, 151 insertions(+), 80 deletions(-) diff --git a/libsepol/cil/src/cil_internal.h b/libsepol/cil/src/cil_internal.h index a77c9520..b8610976 100644 --- a/libsepol/cil/src/cil_internal.h +++ b/libsepol/cil/src/cil_internal.h @@ -48,8 +48,9 @@ #define CIL_MAX_NAME_LENGTH 2048 -#define CIL_DEGENERATE_INHERITANCE_DEPTH 12 -#define CIL_DEGENERATE_INHERITANCE_BREADTH (0x1 << CIL_DEGENERATE_INHERITANCE_DEPTH) +#define CIL_DEGENERATE_INHERITANCE_DEPTH 10UL +#define CIL_DEGENERATE_INHERITANCE_MINIMUM (0x01 << CIL_DEGENERATE_INHERITANCE_DEPTH) +#define CIL_DEGENERATE_INHERITANCE_GROWTH 10UL enum cil_pass { CIL_PASS_INIT = 0, diff --git a/libsepol/cil/src/cil_resolve_ast.c b/libsepol/cil/src/cil_resolve_ast.c index 77ffe0ff..09764e26 100644 --- a/libsepol/cil/src/cil_resolve_ast.c +++ b/libsepol/cil/src/cil_resolve_ast.c @@ -62,6 +62,7 @@ struct cil_args_resolve { struct cil_list *catorder_lists; struct cil_list *sensitivityorder_lists; struct cil_list *in_list; + int *inheritance_check; }; static struct cil_name * __cil_insert_name(struct cil_db *db, hashtab_key_t key, struct cil_tree_node *ast_node) @@ -2306,40 +2307,7 @@ exit: return rc; } -int cil_resolve_blockinherit_link(struct cil_tree_node *current, void *extra_args) -{ - struct cil_blockinherit *inherit = current->data; - struct cil_symtab_datum *block_datum = NULL; - struct cil_tree_node *node = NULL; - int rc = SEPOL_ERR; - - rc = cil_resolve_name(current, inherit->block_str, CIL_SYM_BLOCKS, extra_args, &block_datum); - if (rc != SEPOL_OK) { - goto exit; - } - - node = NODE(block_datum); - - if (node->flavor != CIL_BLOCK) { - cil_log(CIL_ERR, "%s is not a block\n", cil_node_to_string(node)); - rc = SEPOL_ERR; - goto exit; - } - - inherit->block = (struct cil_block *)block_datum; - - if (inherit->block->bi_nodes == NULL) { - cil_list_init(&inherit->block->bi_nodes, CIL_NODE); - } - cil_list_append(inherit->block->bi_nodes, CIL_NODE, current); - - return SEPOL_OK; - -exit: - return rc; -} - -void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_tree_node *terminating_node) +static void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_tree_node *terminating_node) { struct cil_list *trace = NULL; struct cil_list_item *item = NULL; @@ -2377,7 +2345,7 @@ void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_ cil_list_destroy(&trace, CIL_FALSE); } -int cil_check_recursive_blockinherit(struct cil_tree_node *bi_node) +static int cil_check_recursive_blockinherit(struct cil_tree_node *bi_node) { struct cil_tree_node *curr = NULL; struct cil_blockinherit *bi = NULL; @@ -2410,53 +2378,67 @@ exit: return rc; } -/* - * Detect degenerate inheritance of the form: - * ... - * (blockinherit ba) - * (block ba - * (block b1 - * (blockinherit bb) - * ) - * (block bb - * (block b2 - * (blockinherit bc) - * ) - * (block bc - * ... - */ -static int cil_check_for_degenerate_inheritance(struct cil_tree_node *current) +static int cil_possible_degenerate_inheritance(struct cil_tree_node *node) { - struct cil_block *block = current->data; - struct cil_tree_node *node; - struct cil_list_item *item; - unsigned depth; - unsigned breadth = 0; + unsigned depth = 1; - cil_list_for_each(item, block->bi_nodes) { - breadth++; - } - - if (breadth >= CIL_DEGENERATE_INHERITANCE_BREADTH) { - node = current->parent; - depth = 0; - while (node && node->flavor != CIL_ROOT) { - if (node->flavor == CIL_BLOCK) { - block = node->data; - if (block->bi_nodes != NULL) { - depth++; + node = node->parent; + while (node && node->flavor != CIL_ROOT) { + if (node->flavor == CIL_BLOCK) { + if (((struct cil_block *)(node->data))->bi_nodes != NULL) { + depth++; + if (depth >= CIL_DEGENERATE_INHERITANCE_DEPTH) { + return CIL_TRUE; } } - node = node->parent; } + node = node->parent; + } - if (depth >= CIL_DEGENERATE_INHERITANCE_DEPTH) { - cil_tree_log(current, CIL_ERR, "Degenerate inheritance detected (depth=%u, breadth=%u)", depth, breadth); - return SEPOL_ERR; - } + return CIL_FALSE; +} + +int cil_resolve_blockinherit_link(struct cil_tree_node *current, void *extra_args) +{ + struct cil_args_resolve *args = extra_args; + struct cil_blockinherit *inherit = current->data; + struct cil_symtab_datum *block_datum = NULL; + struct cil_tree_node *node = NULL; + int rc = SEPOL_ERR; + + rc = cil_resolve_name(current, inherit->block_str, CIL_SYM_BLOCKS, extra_args, &block_datum); + if (rc != SEPOL_OK) { + goto exit; + } + + node = NODE(block_datum); + + if (node->flavor != CIL_BLOCK) { + cil_log(CIL_ERR, "%s is not a block\n", cil_node_to_string(node)); + rc = SEPOL_ERR; + goto exit; + } + + inherit->block = (struct cil_block *)block_datum; + + rc = cil_check_recursive_blockinherit(current); + if (rc != SEPOL_OK) { + goto exit; + } + + if (inherit->block->bi_nodes == NULL) { + cil_list_init(&inherit->block->bi_nodes, CIL_NODE); + } + cil_list_append(inherit->block->bi_nodes, CIL_NODE, current); + + if (*(args->inheritance_check) == CIL_FALSE) { + *(args->inheritance_check) = cil_possible_degenerate_inheritance(node); } return SEPOL_OK; + +exit: + return rc; } int cil_resolve_blockinherit_copy(struct cil_tree_node *current, void *extra_args) @@ -2475,11 +2457,6 @@ int cil_resolve_blockinherit_copy(struct cil_tree_node *current, void *extra_arg db = args->db; - rc = cil_check_for_degenerate_inheritance(current); - if (rc != SEPOL_OK) { - goto exit; - } - // Make sure this is the original block and not a merged block from a blockinherit if (current != block->datum.nodes->head->data) { rc = SEPOL_OK; @@ -3579,6 +3556,88 @@ exit: return rc; } +/* + * Degenerate inheritance leads to exponential growth of the policy + * It can take many forms, but here is one example. + * ... + * (blockinherit ba) + * (block b0 + * (block b1 + * (block b2 + * (block b3 + * ... + * ) + * (blockinherit b3) + * ) + * (blockinherit b2) + * ) + * (blockinherit b1) + * ) + * (blockinherit b0) + * ... + * This leads to 2^4 copies of the content of block b3, 2^3 copies of the + * contents of block b2, etc. + */ +static unsigned cil_count_actual(struct cil_tree_node *node) +{ + unsigned count = 0; + + if (node->flavor == CIL_BLOCKINHERIT) { + count += 1; + } + + for (node = node->cl_head; node; node = node->next) { + count += cil_count_actual(node); + } + + return count; +} + +static unsigned cil_count_potential(struct cil_tree_node *node, unsigned max) +{ + unsigned count = 0; + + if (node->flavor == CIL_BLOCKINHERIT) { + struct cil_blockinherit *bi = node->data; + count += 1; + if (bi->block) { + count += cil_count_potential(NODE(bi->block), max); + if (count > max) { + return count; + } + } + } + + for (node = node->cl_head; node; node = node->next) { + count += cil_count_potential(node, max); + if (count > max) { + return count; + } + } + + return count; +} + +static int cil_check_for_degenerate_inheritance(struct cil_tree_node *node) +{ + uint64_t num_actual, num_potential, max; + + num_actual = cil_count_actual(node); + + max = num_actual * CIL_DEGENERATE_INHERITANCE_GROWTH; + if (max < CIL_DEGENERATE_INHERITANCE_MINIMUM) { + max = CIL_DEGENERATE_INHERITANCE_MINIMUM; + } + + num_potential = cil_count_potential(node, max); + + if (num_potential > max) { + return SEPOL_ERR; + } + + return SEPOL_OK; +} + int __cil_resolve_ast_node(struct cil_tree_node *node, void *extra_args) { int rc = SEPOL_OK; @@ -4054,6 +4113,7 @@ int cil_resolve_ast(struct cil_db *db, struct cil_tree_node *current) struct cil_args_resolve extra_args; enum cil_pass pass = CIL_PASS_TIF; uint32_t changed = 0; + int inheritance_check = 0; if (db == NULL || current == NULL) { return rc; @@ -4072,6 +4132,7 @@ int cil_resolve_ast(struct cil_db *db, struct cil_tree_node *current) extra_args.catorder_lists = NULL; extra_args.sensitivityorder_lists = NULL; extra_args.in_list = NULL; + extra_args.inheritance_check = &inheritance_check; cil_list_init(&extra_args.disabled_optionals, CIL_NODE); cil_list_init(&extra_args.sidorder_lists, CIL_LIST_ITEM); @@ -4096,6 +4157,15 @@ int cil_resolve_ast(struct cil_db *db, struct cil_tree_node *current) cil_list_destroy(&extra_args.in_list, CIL_FALSE); } + if (pass == CIL_PASS_BLKIN_LINK && inheritance_check == CIL_TRUE) { + rc = cil_check_for_degenerate_inheritance(current); + if (rc != SEPOL_OK) { + cil_log(CIL_ERR, "Degenerate inheritance detected\n"); + rc = SEPOL_ERR; + goto exit; + } + } + if (pass == CIL_PASS_MISC1) { db->sidorder = __cil_ordered_lists_merge_all(&extra_args.sidorder_lists, NULL); if (db->sidorder == NULL) {