linux-kernel - Re: [PATCH v2 1/2] kconfig: fix bad syntactic transformation in expr.c

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Tue, 07 Oct 2014 11:21:51 +0200
From:	Dirk Gouders <dirk@...ders.net>
To:	Paul Bolle <pebolle@...cali.nl>
Cc:	Martin Walch <walch.martin@....de>, yann.morin.1998@...e.fr,
	Michal Marek <mmarek@...e.cz>, linux-kbuild@...r.kernel.org,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2 1/2] kconfig: fix bad syntactic transformation in expr.c

CC: Michal added

Paul Bolle <pebolle@...cali.nl> writes:

> On Mon, 2014-09-22 at 19:13 +0200, Martin Walch wrote:
>> expr_eliminate_dups2() in scripts/kconfig/expr.c applies two bad
>> inference rules:
>> 
>> (FOO || BAR) && (!FOO && !BAR) -> n
>> (FOO && BAR) || (!FOO || !BAR) -> y
>> 
>> They would be correct in propositional logic, but this is a three-valued
>> logic, and here it is wrong in that it changes semantics. It becomes
>> immediately visible when substituting FOO and BAR with m.
>
> Well, not to me. When I apply the rules under "Menu dependencies" in
> Documentation/kbuild/kconfig-language.txt, in embarrassingly small
> steps, I get:
>     (m || m) && (!m && !m) ->
>     (1 || 1) && ((2 - 1) && (2 - 1)) ->
>     (1 || 1) && (1 && 1) ->
>     max(1, 1) && min(1, 1) ->
>     1 && 1 ->
>     min(1, 1) ->
>     1 -> m
>
> and
>     (m && m) || (!m || !m) ->
>     (1 && 1) || ((2 - 1) || (2 - 1)) ->
>     (1 && 1) || (1 || 1) ->
>     min(1, 1) || max(1, 1) ->
>     1 || 1 ->
>     max(1, 1) ->
>     1 -> m
>
> Did I do that right? Anyway, perhaps you'd like to add a line or two how
> these two expressions actually evaluate when FOO and BAR are m.

Perhaps, it helps to use a Kconfig file that visualizes the problem:

mainmenu "Expr Test"

config expr-config
	bool "Expr Config"
	depends on (m || m) && (!m && !m)
#	depends on (m && m) || (!m || !m)

config dummy
       bool "Dummy"

config modules
       bool
       option modules
       default y

Those two depends, according to your calculation and if I understood
correctly also to Martin's, should evaluate to 'm' and thus the menu
entry should always be visible, because both depends should evaluate to
'm'.  But because of expr_eliminate_dups2() it is either invisible (the
first depends becomes 'n') or always visible (the second depends becomes
'y').

Dirk

>> Fix it by removing expr_eliminate_dups2() and the functions that have no use
>> anywhere else: expr_extract_eq_and(), expr_extract_eq_or(),
>> and expr_extract_eq() from scripts/kconfig/expr.[ch]
>> 
>> Currently the bug is not triggered in mainline, so this patch does not modify
>> the configuration space there.
>> 
>> As a side effect, this reduces code size in expr.c by roughly 10% and slightly
>> improves startup time for all configuration frontends.
>> 
>> Signed-off-by: Martin Walch <walch.martin@....de>
>
> Does Yann still care about Kconfig? Yann has been rather quiet for a
> while now.
>
>
> Paul Bolle
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
> the body of a message to majordomo@...r.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/