From patchwork Sat Nov 16 05:17:06 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Hurukawa2121 X-Patchwork-Id: 3946 Return-Path: Delivered-To: patchwork@openvpn.net Received: by 2002:a05:7000:1ee:b0:5d9:9f4c:3bc7 with SMTP id 14csp1451521map; Fri, 15 Nov 2024 21:31:58 -0800 (PST) X-Forwarded-Encrypted: i=2; AJvYcCVttWuIi6FOOrKcQN81zh5IVOTWNl/6VNz0dvASc7O3LZEfua9y8CkaCBHJjx1IdZ0ZgGdfOd53iEI=@openvpn.net X-Google-Smtp-Source: AGHT+IE5UhD8uwU4+pAWMJ7gXukpbW+OsZQBuwwHbpE+Y1git8RX7uKsNpZW05kENDzuaT5aB2Cd X-Received: by 2002:a05:6e02:1529:b0:3a6:abdc:dfbe with SMTP id e9e14a558f8ab-3a7480377bdmr45341005ab.14.1731735117926; Fri, 15 Nov 2024 21:31:57 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1731735117; cv=none; d=google.com; s=arc-20240605; b=Iu5Y9cotU629jWFFntYChetQ4c0tEu9138ZL1wFWcnzmsvAmlRr8xViM2EbDoICScO qel8lqSxjmHEQDNDK9AyBbrjBfobOlVQNLQmNjuGKichDec2MXnPFlwv2VfjCtxsKguY qyYnVS6EuoyiJBqFk/mS1faw1koCvhhWHI/zB7pL6eMJbSXzEPJIS9ScEAYJtNOF3MSM svf7H0O5EIfVjyhNxd7G0othePxL927UmqvWMEpv6SDm7X9eruyb4NCUznreBkM/scg/ MtxGVg1ci72gOFUJwJQcwLwP0D06J8udLo+Kppj0E7thNAFQN0D1wqxMC5bBYLyUle1S 7pjQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=errors-to:content-transfer-encoding:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence:subject :mime-version:message-id:date:to:from:dkim-signature:dkim-signature :dkim-signature; bh=pvU7lGNfRuWSa3vG0xW7GlwtPF8gP1P13gAvkkVMybU=; fh=4NbAC/LsuMLI0S0hprUlLSLCiHwg6SCAifhH718Jh0Q=; b=ETUESq+VJbbMZRYt0t1X1covLRwAY9fKASC/GQlRq+FF8XIrGSRoIPlxv7pruiznMK 8JON1nH+7qTCnTBc02oVwa3P+nScCYHJOsioVzcxujB/g50XqR9Z5+9XieiUy1qIUdge YB0djCEfejhvAB8xdgfaF/Wj31O6Ltlyf2YLjkkcxYJRTUxhWvjUVdqVcWl+beZ9Q2Jo 0IYhJjoaKdiUrnk7SizY6Pv+YhCTk6Lo6I75DLXfpo97cFF0C+wu0EZetscbYOiH3VjD zg6sfHkbB3kXKviAtzsLfqTr+3r8SxUV/Tuea4W4sEdy4PYXgcE1Pn/kti4oBe0yydkX NNGA==; dara=google.com ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@sourceforge.net header.s=x header.b=SZfpdtGn; dkim=neutral (body hash did not verify) header.i=@sf.net header.s=x header.b=cEwJ7ejt; dkim=neutral (body hash did not verify) header.i=@gmail.com header.s=20230601 header.b=C1TOKAej; spf=pass (google.com: domain of openvpn-devel-bounces@lists.sourceforge.net designates 216.105.38.7 as permitted sender) smtp.mailfrom=openvpn-devel-bounces@lists.sourceforge.net; dmarc=fail (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=fail header.i=@openvpn.net Received: from lists.sourceforge.net (lists.sourceforge.net. [216.105.38.7]) by mx.google.com with ESMTPS id e9e14a558f8ab-3a7481226cbsi24035115ab.113.2024.11.15.21.31.57 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Fri, 15 Nov 2024 21:31:57 -0800 (PST) Received-SPF: pass (google.com: domain of openvpn-devel-bounces@lists.sourceforge.net designates 216.105.38.7 as permitted sender) client-ip=216.105.38.7; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@sourceforge.net header.s=x header.b=SZfpdtGn; dkim=neutral (body hash did not verify) header.i=@sf.net header.s=x header.b=cEwJ7ejt; dkim=neutral (body hash did not verify) header.i=@gmail.com header.s=20230601 header.b=C1TOKAej; spf=pass (google.com: domain of openvpn-devel-bounces@lists.sourceforge.net designates 216.105.38.7 as permitted sender) smtp.mailfrom=openvpn-devel-bounces@lists.sourceforge.net; dmarc=fail (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=fail header.i=@openvpn.net Received: from [127.0.0.1] (helo=sfs-ml-4.v29.lw.sourceforge.com) by sfs-ml-4.v29.lw.sourceforge.com with esmtp (Exim 4.95) (envelope-from ) id 1tCBPN-0007vT-VF; Sat, 16 Nov 2024 05:31:45 +0000 Received: from [172.30.29.66] (helo=mx.sourceforge.net) by sfs-ml-4.v29.lw.sourceforge.com with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1tCBPN-0007vK-3o for openvpn-devel@lists.sourceforge.net; Sat, 16 Nov 2024 05:31:45 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=sourceforge.net; s=x; h=Content-Transfer-Encoding:MIME-Version:Message-Id: Date:Subject:Cc:To:From:Sender:Reply-To:Content-Type:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:In-Reply-To:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=uKu3Ob3uQlK5H6Bi+bxZcHS4slpKBFkK4dCNqcbiaeY=; b=SZfpdtGnbzVsdq3AzhCMAubnXD u9Ij90saEe3MZoFqDdlonuuwPw25Etm6XcZAWSbDIl6nXHBb5XP+QBfC7qSk4qDIWXtWfADtgYUIE XDJ9mX2lt++Eu866ojm3gOQOxYf9nAP051UwYSPvQXztw43jD7+uhqEZZD2Cqd6vNhZc=; DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=sf.net; s=x ; h=Content-Transfer-Encoding:MIME-Version:Message-Id:Date:Subject:Cc:To:From :Sender:Reply-To:Content-Type:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To: References:List-Id:List-Help:List-Unsubscribe:List-Subscribe:List-Post: List-Owner:List-Archive; bh=uKu3Ob3uQlK5H6Bi+bxZcHS4slpKBFkK4dCNqcbiaeY=; b=c EwJ7ejt3/er+z5pdi37WrGUvvxlqxf7/0r9c0ByTBVzTC/oT1xTZKHkr2InYWqyHIeSmBKPfWskqc ATsGOLeI1wLrQWfPwwrmQYF/I4iqF56Tu+khvKpggYxRa6mrT7Sr0uQAQ4ZxMmSgFZOCAZmJPvsZz gz1Y0Jih1UU5I1WI=; Received: from mail-pg1-f182.google.com ([209.85.215.182]) by sfi-mx-2.v28.lw.sourceforge.com with esmtps (TLS1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (Exim 4.95) id 1tCBPM-0005AV-3s for openvpn-devel@lists.sourceforge.net; Sat, 16 Nov 2024 05:31:44 +0000 Received: by mail-pg1-f182.google.com with SMTP id 41be03b00d2f7-7f3da2c2cb5so1879486a12.2 for ; Fri, 15 Nov 2024 21:31:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731735093; x=1732339893; darn=lists.sourceforge.net; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=uKu3Ob3uQlK5H6Bi+bxZcHS4slpKBFkK4dCNqcbiaeY=; b=C1TOKAejm6puEQszTDBmktddFp6ms1sPqEshiIrXRsqCaa6pBURdjfxvu6p+bbjTC6 boQhoFMHDBUX3Z+RBXQUS7Fp8RR9OtJFwcg3zfUuDjhVldNbERbPdpF3DgG26arydXXG cMBOA8h36vIWahMxDPtCoGjZAT86hWTizeSSCS7KxXilUcwLxLoT7CVJnZXThyepLaqA jdcKnt0G3FoBaUG9sHwZz/9JdxcKBbufM0bYzEqnzabSkGiIjIWdb8cWizHr6fqZ3cVY ucz+c9EU0aWionHQ6xyn2IagsuKvncV+uayZd10AdPLyQTvQ9qUhq+QYy887NTieyZZX C2+A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731735093; x=1732339893; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=uKu3Ob3uQlK5H6Bi+bxZcHS4slpKBFkK4dCNqcbiaeY=; b=uKiFUEaqr8ma/OCNHW7l1kQdltOg3BaBgCp7SCyt0DN7xAaijOvskj+HdQGv1boJqf tAgZJAn7x87drvRvjsQxYKCnge0pgIXXZIZp4Yl5Hb5xVzh9dmx6D2zDpR7oawr3Nr4e ILWuog7S3iFWh/yjcBNxlhSKY5pyNRrDGQcNFw5hznAROLVdnaGxamVE2YthCipKCBM2 Y8m4yYT+ku8FrqtFQyqZNkIghBgp94peCBVW8AnVqFz54kpaX0tYAuerM3TRujsq0+Sy KZ3OL0xAwQaSviFpPCam3jxwlSTQNM9WZ2mUKJgFo8Ho01oGcJOS1uoU61CtC5C0Wlvv pMQg== X-Gm-Message-State: AOJu0Ywh08a1jEULyTLd3rHwotNLEDejO8Zm5TP+VK83OfFckSV4Mqd+ dr4eWGLlBqdV3tFNtNzslz05kBWK9H83JWgskiOtX1Yv0EcmRWVv01DIUA== X-Received: by 2002:a05:6a20:7344:b0:1db:f960:bda8 with SMTP id adf61e73a8af0-1dc90bde950mr7137236637.34.1731735093392; Fri, 15 Nov 2024 21:31:33 -0800 (PST) Received: from localhost.localdomain ([2001:268:9874:1d91:81a2:efdd:a05e:1258]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-7f8c1c5e528sm2233452a12.35.2024.11.15.21.31.31 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 15 Nov 2024 21:31:32 -0800 (PST) From: Hurukawa2121 To: openvpn-devel@lists.sourceforge.net Date: Sat, 16 Nov 2024 14:17:06 +0900 Message-Id: <20241116051705.53061-1-shujifurukawa1213@gmail.com> X-Mailer: git-send-email 2.39.3 (Apple Git-146) MIME-Version: 1.0 X-Spam-Score: 0.1 (/) X-Spam-Report: Spam detection software, running on the system "util-spamd-2.v13.lw.sourceforge.com", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: --- Improve shuffling algorithm of connection list This patch implements the Fisher-Yates shuffle algorithm to ensure that all permutations of the connection target list are generated with equal probability, eliminating biases present in the previous [...] Content analysis details: (0.1 points, 6.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider [shujifurukawa1213[at]gmail.com] 0.2 FREEMAIL_ENVFROM_END_DIGIT Envelope-from freemail username ends in digit [shujifurukawa1213[at]gmail.com] -0.0 SPF_PASS SPF: sender matches SPF record 0.0 RCVD_IN_VALIDITY_SAFE_BLOCKED RBL: ADMINISTRATOR NOTICE: The query to Validity was blocked. See https://knowledge.validity.com/hc/en-us/articles/20961730681243 for more information. [209.85.215.182 listed in sa-trusted.bondedsender.org] 0.0 RCVD_IN_VALIDITY_RPBL_BLOCKED RBL: ADMINISTRATOR NOTICE: The query to Validity was blocked. See https://knowledge.validity.com/hc/en-us/articles/20961730681243 for more information. [209.85.215.182 listed in bl.score.senderscore.com] 0.0 RCVD_IN_MSPIKE_H3 RBL: Good reputation (+3) [209.85.215.182 listed in wl.mailspike.net] -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at https://www.dnswl.org/, no trust [209.85.215.182 listed in list.dnswl.org] -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID_EF Message has a valid DKIM or DK signature from envelope-from domain -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.0 RCVD_IN_MSPIKE_WL Mailspike good senders X-Headers-End: 1tCBPM-0005AV-3s Subject: [Openvpn-devel] [PATCH] Improve shuffling algorithm of connection list X-BeenThere: openvpn-devel@lists.sourceforge.net X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: openvpn-devel-bounces@lists.sourceforge.net X-getmail-retrieved-from-mailbox: Inbox X-GMAIL-THRID: =?utf-8?q?1815818427618448736?= X-GMAIL-MSGID: =?utf-8?q?1815855883038980260?= --- Improve shuffling algorithm of connection list This patch implements the Fisher-Yates shuffle algorithm to ensure that all permutations of the connection target list are generated with equal probability, eliminating biases present in the previous shuffling method. In the Fisher-Yates algorithm, there's only one way to obtain each permutation through a series of element swaps, so all permutations occur with equal probability in theory. Signed-off-by: Hurukawa2121 src/openvpn/init.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) diff --git a/src/openvpn/init.c b/src/openvpn/init.c index 9371024e..c4fb5cd7 100644 --- a/src/openvpn/init.c +++ b/src/openvpn/init.c @@ -467,7 +467,14 @@ ce_management_query_remote(struct context *c) #endif /* ENABLE_MANAGEMENT */ /* - * Initialize and possibly randomize connection list. + * Initialize and randomize the connection list. + * + * Applies the Fisher-Yates shuffle algorithm to ensure all permutations are equally probable, + * thereby eliminating shuffling bias in the previous method. + * + * The algorithm randomly selects an element from the unshuffled portion and places it at position i. + * There's only one way to obtain each permutation through these swaps. + * This guarantees that each permutation occurs with equal probability in theory. */ static void init_connection_list(struct context *c) @@ -478,9 +485,9 @@ init_connection_list(struct context *c) if (c->options.remote_random) { int i; - for (i = 0; i < l->len; ++i) + for (i = l->len - 1; i > 0; --i) { - const int j = get_random() % l->len; + const int j = get_random() % (i + 1); if (i != j) { struct connection_entry *tmp;